1、算法思想

将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。

即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

2、代码实现

package sort;

public class StraightInsertSort {

    public static void main(String[] args) {
        int[] source = {99, 53, 27, 36, 15, 69, 42, 66};
        printArr(source);
        StraightInsertSort(source);
        printArr(source);
    }

    /**
     * 将一个记录插入到已排序好的有序表中，从而得到一个新的记录数增1的有序表。 即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 要点：设立哨兵，作为临时存储和判断数组边界之用。
     */
    private static void StraightInsertSort(int[] source) {
        if (source.length <= 1 || source == null) {
            return;
        }
        int j;
        for (int i = 1; i < source.length; i++) { // 从第二个数开始，依次直接插入
            j = i;// 亦可只用一个变量i，但会增加比较次数
            while (j > 0 && source[j] < source[j - 1]) {// 位置不合适则交换
                source[j] = source[j - 1] + (source[j - 1] = source[j]) * 0;
                j--;
            }
            printArr(source);
        }
    }

    private static void printArr(int[] source) {
        for (int i : source) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

3、算法分析

算法稳定性

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。

最好情况：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。

最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次（计算式为1+2+……+ n-1）。

直接插入排序属于稳定的排序，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。

插入排序的赋值操作是比较操作的次数加上(n-1)次。

因此，插入排序不适合对于数据量比较大的排序应用。

源码地址：https://github.com/zxiaofan/Algorithm/blob/master/src/sort/StraightInsertSort.java