插入排序

1 直接插入排序

直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序袭。

思路

如第 0 到 5 范围内的数从小到大排列，第六个数记为 temp，此时第 temp 比第 5 个数小，那么第 5 个数往后退，接着再与第 4 个数比较，如果还是比第 4 个数小，那么第 4 个数继续后退，接着如果不小于第 3 个数，这个时候将 temp 存到 4 的位置 。总的来说，就是在一个有序范围内，插入一个该范围之外的数，随着执行下，有序范围逐渐扩大，最后整体有序。

public static void insert(int array[]){
    for (int i = 1; i < array.length; i++) {
        int temp=array[i];
        int j=i;
        while(j>0&&temp<array[j-1]){
            array[j]=array[j-1];
            j--;
        }
        array[j]=temp;
    }
}

复杂度分析

同样的 O(n²) 时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

2 希尔排序

思路

希尔排序是在插入排序的基础上进一步改进的。

• 插入排序每一次移动只能移动一位，而希尔排序可以按步长移动。
• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。

针对这两点，希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

总的来说，希尔排序的最后一步是插入排序，但是在插入排序之前，实现了基本有序。

public static void shell(int array[]){
    int gap = array.length/2;
    //控制步长
    while(gap!=0){
        for (int i = 0; i < gap; i++) {
            //插入排序
            for (int j = i+gap; j < array.length; j=j+gap) {
                int temp=array[j];
                int p=j;
                while(p>=gap&&temp<array[p-gap]){
                    array[p]=array[p-gap];
                    p=p-gap;
                }
                array[p]=temp;
            }
        }
        gap=gap/2;
    }
}

复杂度分析

选好增量序列，可以达到O(n^3/2)