插入排序的基本方法是：每步将一个待排序的元素，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。插入排序主要有直接插入排序、二分插入排序、希尔排序，本章主要介绍希尔排序。

算法思想

希尔排序是第一批突破O(n²)的排序算法之一，它是针对直接插入排序的改进，属于插入排序。

从插入排序的特点中可以看出如果待排序列元素较少或者待排序列有序度较高，那么排序的速度会较快，因此希尔排序的思想是将待排序列按照增量分组（每组元素减少），组内直接插入排序，然后不断缩小这个增量继续排序（每组元素增加但待排序列的有序度变高），当gap为1排序后序列有序，因此希尔排序又称缩小增量排序。

举一个最简单的例子，待排序列为4，3，2，1：

初始gap为array.length/2为2，即4，2为一组，3，1为一组
组内进行直接插入排序，可以交换或者移动，排序后的序列为2，1，4，3
gap/=2后gap为1，整个序列都为一组，->1, 2, 4, 3 -> 1, 2, 4, 3 -> 1, 2, 3, 4
gap/=2后gap为0，排序结束

分析可以看出元素1回到头处比较和移动都为两次，而直接插入排序比较和移动都需要三次，究其原因是直接插入排序的增量都为1，而希尔排序的增量是跳跃式的，相应地也减少了比较和移动的次数

代码实现

public class Shellsort {
    public static void main(String[] args) {
        int[] array = new int[]{5,2,4,1,6,8,10,7,9,3};

        shellsort(array);

        for (int j : array) {
            System.out.println(j);
        }
    }

    public static void shellsort(int[] array){
        //gap从array.length/2开始，gap/=2
        for(int gap = array.length/2; gap>0; gap/=2){
          	//从索引为gap的元素开始遍历
            for (int i=gap; i<array.length; i++) {
                int j = i;
                int temp = array[j];
              	//同组所有比temp大的元素向右移动
              	//比如5, 2, 4, 3, 6, 1;此时i为5，j也为5，temp为1，gap为2
                //->5, 2, 4, 3, 6, 3; j为3
                //->5, 2, 4, 2, 6, 3; j为1
                while(j - gap >= 0 && temp < array[j-gap]) {
                    array[j] = array[j - gap];
                    j -= gap;
                }
                //留下的空位放temp
                //->5, 1, 4, 2, 6, 3; array[j] = temp -> array[1] = 1;
                array[j] = temp;
            }
        }
    }
}

复杂度

时间复杂度

希尔排序的时间复杂度根据步长序列的不同而不同，总的来说希尔排序的时间复杂度小于O(n²)，但没有快速排序(平均为O(nlogn))快；

最好的步长序列为从第0项开始，偶数来自9×4ⁱ−9×2ⁱ+1和奇数来自2ⁱ⁺²×(2ⁱ⁺²−3)+1这两个算式，此时最好的最差时间复杂度为O(nlog²n);

通常使用的n/2ⁱ，最差时间复杂度为O(n²);

最好时间复杂度为O(n)

空间复杂度

O(1)，额外一个空间用于存放temp值

稳定性

当待排序列为2，2*，1，4，gap为2时，排序后为1，2*，2，4，两个2的相对顺序改变，因此希尔排序不稳定

总结

排序算法	时间复杂度	空间复杂度	稳定性
希尔排序	最好为O(n)，最差和平均根据步长序列不同而不同，最好的最坏复杂度为O(nlog²n)	O(1)	稳定

插入排序之希尔排序

Effy

算法思想

代码实现

复杂度

时间复杂度

空间复杂度

稳定性

总结

Other Articles

插入排序之直接插入排序

排序算法之二———归并排序