概述

算法描述：对于给定的一个数组，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
空间复杂度O(1)
时间复杂度O(n^2)

代码

package test;

import java.util.Arrays;

/**
 * Created by liqiushi on 2018/1/10.
 */
public class InsertionSort {

    private static void sort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    int tmp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int a[] = new int[]{1, 5, 8, 4, 6, 78, 26, 13, 66};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

}