设数组为a[0…n-1]。

1. 初始时，a[1]自成1个有序区（a[0]作为哨兵），无序区为a[2..n-1]。令i=1

2. 将a[i]并入当前的有序区a[1…i-1]中：（将比a[i]大的往后移,直到找到<=a[i]的数，把a[i]插入到这个数的后面位置），形成a[0…i]的有序区间。

3. i++并重复第二步直到i==n-1。排序完成。

代码：

public class DirectInsertionSort {
    public static void main(String[] args) {
        int[] toBeSorted = { 0, 1, 3, 5, 2, 4, 6, 0, -1 };
        for (int i = 2; i < toBeSorted.length; i++) {
            if (toBeSorted[i] < toBeSorted[i - 1]) {// 如果toBeSorted[i]没有按顺序
                // 把它的值保存在哨兵中
                toBeSorted[0] = toBeSorted[i];
                int j = i - 1;
                for (; toBeSorted[j] > toBeSorted[0]; j--) {
                    toBeSorted[j + 1] = toBeSorted[j];
                }
                // 然后把toBeSorted[i]放到那个位置
                toBeSorted[j+1] = toBeSorted[0];
            }
        }
        for (int p = 1; p < toBeSorted.length; p++) {
            System.out.print(toBeSorted[p]);
        }
        System.out.println();
    }
}

//简化版
for (int i = 1; i < toBeSorted.length; i++) {
    for (int j = i - 1; j >= 0 && toBeSorted[j] > toBeSorted[j + 1]; j--) {
        int t = toBeSorted[j];
        toBeSorted[j] = toBeSorted[j + 1];
        toBeSorted[j + 1] = t;
    }
}

时间复杂度

O(n^2)

稳定性

是稳定的