排序算法丨希尔排序

前言

希尔排序(Shell's Sort)，是插入排序的一种，也是直接插入排序算法的一种更高效的改进版本。

1959年7月，美国辛辛那提大学的数学系博士 Donald Shell 在《ACM 通讯》上发表了希尔排序算法，成为首批将时间复杂度降到 O(n²) 以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是 O(n²)，但经过优化的希尔排序可以达到 O(n^1.3) 甚至 O(n^7/6)。该方法以其设计者希尔（Donald Shell）的名字命名，所以就叫希尔排序。

希尔排序是非稳定的排序算法。

排序思路

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

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

它的基本思想：

将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组。
逐渐缩小间隔进行下一轮排序。
最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的“宏观调控”，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成。

增量序列

其中，每一遍排序的间隔在希尔排序中被称之为增量，所有的增量组成的序列称之为增量序列。
增量依次递减，最后一个增量必须为 1，所以希尔排序又被称之为“缩小增量排序(Diminishing Increment Sort)”。

要是以专业术语来描述希尔排序，可以分为两个步骤：

定义增量序列 D_m > D_m-1 > D_m-2 > ... > D₁ = 1
对每个 D_k 进行 “D_k 间隔排序“
有一条非常重要的性质保证了希尔排序的效率：
"D_k+1 间隔” 有序的序列，在经过 “D_k 间隔” 排序后，仍然是 “D_k+1 间隔” 有序的。

增量序列的选择会极大地影响希尔排序的效率。

一般使用的逐步减半的增量序列为 D_m = N/2，D_k = D_k+1/2，这个序列是当年希尔发表此算法的论文中选用的序列，所以也被称之为希尔增量序列。

代码实现

public static void shellSort1(int[] arr) {
    // 间隔序列，在希尔排序中我们称之为增量序列
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 分组
        for (int groupStartIndex = 0; groupStartIndex < gap; groupStartIndex++) {
            // 插入排序
            for (int currentIndex = groupStartIndex + gap; currentIndex < arr.length; currentIndex += gap) {
                // currentNumber 站起来，开始找位置
                int currentNumber = arr[currentIndex];
                int preIndex = currentIndex - gap;
                while (preIndex >= groupStartIndex && currentNumber < arr[preIndex]) {
                    // 向后挪位置
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                // currentNumber 找到了自己的位置，坐下
                arr[preIndex + gap] = currentNumber;
            }
        }
    }
}

代码优化

处理完一组间隔序列后，再回来处理下一组间隔序列这种方式，这非常符合人类思维。
但对于计算机来说，它更喜欢从第 gap 个元素开始，按照顺序将每个元素依次向前插入自己所在的组这种方式。
虽然这个过程看起来是在不同的间隔序列中不断跳跃，但让计算机连续访问一段数组显然效率更高。

public static void shellSort(int[] arr) {
    // 间隔序列，在希尔排序中我们称之为增量序列
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从 gap 开始，按照顺序将每个元素依次向前插入自己所在的组
        for (int i = gap; i < arr.length; i++) {
            // currentNumber 站起来，开始找位置
            int currentNumber = arr[i];
            // 该组前一个数字的索引
            int preIndex = i - gap;
            while (preIndex >= 0 && currentNumber < arr[preIndex]) {
                // 向后挪位置
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;
            }
            // currentNumber 找到了自己的位置，坐下
            arr[preIndex + gap] = currentNumber;
        }
    }
}

经过优化之后，这段代码看起来就和插入排序非常相似了，区别仅在于希尔排序最外层嵌套了一个缩小增量的 for 循环；并且插入时不再是相邻数字挪动，而是以增量为步长挪动。

选择合适的增量序列

增量序列如果选得不好，希尔排序的效率可能比插入排序效率还要低，最坏的时间复杂度依然是 O(n²)。

如下图所示：

在这个例子中，可以发现，原数组 4 间隔、2 间隔都已经有序了，使用希尔排序时，真正起作用的只有最后一轮 1 间隔排序，也就是直接插入排序。对于这种数组，希尔排序并没有减少直接插入排序的工作量，反而增加了分组操作的成本。

于是人们发现：增量元素不互质，则小增量可能根本不起作用。

为了保证每一轮的增量需要彼此互质（除了 1 以外没有其他公约数），人们相继提出多种增量方式，其中比较著名的有 Hibbard 增量序列、Knuth 增量序列、Sedgewick 增量序列。

动画演示

演示动画来自于Data Structure Visualizations

复杂度分析

事实上，希尔排序时间复杂度非常难以分析，它的平均复杂度界于最好的 O(n) 和最坏的 O(n²) 之间，普遍认为它为 O(n^1.3)。
希尔排序的空间复杂度为 O(1)，只需要常数级的临时变量。

比较

直接插入排序是稳定的，而希尔排序是不稳定的。
直接插入排序可适用于链式存储结构，而希尔排序不适用。
当数据规模越大时，希尔排序相较于直接插入排序的效果更明显。

参考

LeetCode
程序员小灰
 趣谈编程