上期回顾：

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

基本思想

将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。

可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。

算法描述

1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

2. 按增量序列个数 k，对序列进行 k 趟排序；

3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

效果如下：

代码实现

下面参考《算法》中给出的步长选择策略，《算法》中给出的解释是

下面代码中递增序列的计算和使用都很简单，和复杂递增序列的性能接近。当可以证明复杂的序列在最坏情况下的性能要好于我们所使用的递增序列。更加优秀的递增序列有待我们去发现。

public static void sort(int[] a) {
    int length = a.length;
    int h = 1;
    while (h < length / 3) h = 3 * h + 1;
    for (; h >= 1; h /= 3) {
        for (int i = 0; i < a.length - h; i += h) {
            for (int j = i + h; j > 0; j -= h) {
                if (a[j] < a[j - h]) {
                    int temp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = temp;
                }
            }
        }
    }
}

复杂度分析

以下是希尔排序复杂度:

总结与思考

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。