本文共 1261 字，大约阅读时间需要 4 分钟。

直接插入排序算法简单，在n值较小时，效率比较高；当n值比较大师，如果待排序序列是按关键字值基本有序，效率依然很高，可以提高到$O(n)$。希尔排序正式从这两点出发对直接插入排序的改进方法。

希尔排序（Shell Sort）又称为“缩小增量排序”，有D. L. Shell在1959年首先提出来。

基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 dt=1(dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

主要步骤

1. 选择一个增量序列{d0, d1, … ,dk-1}
2. 根据当前增量di将n条记录分成di个子表，每个子表中记录的下标相隔为di
3. 对各个子表中的记录进行直接插入排序
4. 令i=0,1,…，k-1，重复2-4

性能

空间复杂度：与直接插入排序一样为$O(1)$。

时间复杂度：时间效率依赖于增量序列的选取。最好的情况为$O(n)$，最坏的情况为$O(n^2)$。使用Hibbard增量序列时{

稳定性：是不稳定的排序算法。

java代码实现：

/**     * 希尔排序，O(n2)     * 使用shell增量,h(max)=n/2,h(k)=h(k+1)/2;     * Hibbard增量(1, 3, 7, .......2k - 1)的希尔排序的时间复杂度为O(N3/2)       * @param arr     * @return     */    public static 
   
    > void shellSort(T[] arr) {        T tmp = null;        int size = arr.length;        int gap, i, j;        for (gap = size / 2; gap > 0; gap /= 2) {            for (i = gap; i < size; i++) {                tmp = arr[i];                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {                    arr[j] = arr[j - gap];                }                arr[j] = tmp;            }        }    }
   

参考：