突破 O(N^2)：希尔排序

一句话总结

希尔排序是基于 插入排序 的简单改进，通过预处理增加数组的局部有序性，突破了插入排序的 O(n²) 时间复杂度。

必须承认，希尔排序的思路很难想到，我是在《算法 4》第一次了解到这个算法，然后惊叹于这个算法的简单优化竟然能给插入排序带来如此大的提升。

首先我们要明确一个 h 有序数组 的概念。

h 有序数组

一个数组是 h 有序的，是指这个数组中任意间隔为 h（或者说间隔元素的个数为 h-1）的元素都是有序的。

这个概念用文字不好描述清楚，直接看个例子吧。比方说 h=3 时，一个 3 有序数组是这样的：

nums:
[1, 2, 4, 3, 5, 7, 8, 6, 10, 9, 12, 11]
 ^--------^--------^---------^
    ^--------^--------^---------^
       ^--------^--------^----------^

 1--------3--------8---------9
    2--------5--------6---------12
        4--------7--------10---------11

可以看到，[1,3,8,9]、[2,5,6,12]、[4,7,10,11] 这三个数组都是有序的，且元素 1, 3，元素 3, 8，元素 8, 9，元素 2, 5 等等，每一对儿元素的间隔是 3（或者说间隔元素的个数是 2）。

所以我们称上面这个 nums 数组是 3 有序数组。你乍一看整个nums 数组，是无序的，但是每 3 个元素分组后再看，每一组又都是有序的。

另外，按照这个定义，当一个数组完成排序的时候，其实就是 1 有序数组。

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 ^--^--^--^--^--^--^--^--^--^

希尔排序

我在前文插入排序分析过，插入排序对于有序度较高的数组效率很高，直逼 O(n)，但对于有序度低（元素分布较随机）的数组就只有 O(n²) 了。

是否可以优化插入排序，使得即便有序度很低时，其时间复杂度也低于 O(n²) 呢？

希尔排序要发表看法了：

你插入排序的问题是，上来就想着一步到位，直接把乱序数组变成 1 有序数组。而我希尔排序不着急，比方说，我先把乱序数组变成一个 16 有序数组，然后再变成 8 有序数组，4 有序数组，2 有序数组，最后变成 1 有序数组，完成排序。

这个 1, 2, 4, 8, 16... 的序列称之为「递增函数」。

那么如何把一个数组变成 h 有序数组呢？基于插入排序的代码改动几个地方就行了，直接看希尔排序的代码吧：

// 希尔排序，对 h 有序数组进行插入排序
// 逐渐缩小 h，最后 h=1 时，完成整个数组的排序
func sort(nums []int) {
    n := len(nums)
    // 我们使用的生成函数是 2^(k-1)
    // 即 h = 1, 2, 4, 8, 16...
    h := 1
    for h < n/2 {
        h = 2 * h
    }

    // 改动一，把插入排序的主要逻辑套在 h 的 while 循环中
    for h >= 1 {
        // 改动二，sortedIndex 初始化为 h，而不是 1
        sortedIndex := h
        for sortedIndex < n {
            // 改动三，把比较和交换元素的步长设置为 h，而不是相邻元素
            i := sortedIndex
            for i >= h {
                if nums[i] < nums[i-h] {
                    // swap(nums[i], nums[i-h])
                    tmp := nums[i]
                    nums[i] = nums[i-h]
                    nums[i-h] = tmp
                } else {
                    break
                }
                i -= h
            }
            sortedIndex++
        }

        // 按照递增函数的规则，缩小 h
        h /= 2
    }
}

递增函数的选择是关键

希尔排序的性能和递增函数的选择有很大关系

排序稳定性

希尔排序是不稳定排序。

这个比较容易理解吧，当 h 大于 1 时进行的排序操作，就可能打乱相同元素的相对位置了。

时空复杂度分析

希尔排序的空间复杂度是 O(1)，是原地排序算法。

希尔排序的时间复杂度很难分析，主要取决于递增函数的选择，且涉及较多的数学知识，这里就不展开了，不过一个重要结论是：希尔排序的时间复杂度是小于 O(n²) 的。

这一点可以直观感受出来，毕竟前面的 选择排序、冒泡排序 和 插入排序 都过不了第 912 题的所有用例，而希尔排序可以。

建议把 (3k−1)/2 作为递增函数来写希尔排序的代码，这种写法的效率相对较高。

好了，绕了一大圈，终于能够成功通过第 912 题「排序数组」了，有没有感觉到一些小激动？

从希尔排序开始，复杂度为 O(n²)的初级排序算法就告一段落了，接下来的高级排序算法一个比一个能打，当然，也很难通过你自己独立推导出来了。

不过，这些高级排序算法的底层思想还是脱胎于基础数据结构和初级排序算法的，只要你把前面的内容稳扎稳打理解透彻，不需要死记硬背就能把它们随心运用出来了。