希尔排序，冷门但是有趣的排序算法

今天我们继续来聊《算法》第四版这本书，在上一篇文章当中我们复习了一下三种简单的的排序算法，今天我们来稍微进阶一下，来看看稍微更复杂一些的排序算法。

今天选中的算法是希尔排序，它本质上是插入排序的优化。是简单的插入排序改进之后的版本，也成为缩小增量排序。也是第一个突破复杂度的算法。

为了更好地理解它和插入排序之间的差异，我们再来复习一下插入排序：

void insert_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        for (int j = i; j >-1 && nums[j] < nums[j-1] ; j--) {
            swap(nums[j], nums[j-1]);
        }
    }
}

我们每次拿到一个新的数nums[i]时，通过一重循环，将它往前移动到插入的位置。我们分析一下代码会发现一个问题，如果我们在数组的后段遇到了一个较小的元素，那么我们需要经过多次的交换才能让它回到正确的位置上。

比如最后的0，需要跨过整个数组才能到达下标0，这样的元素多了，就会非常影响算法的性能。希尔排序正是针对这个问题的优化，有没有办法能够让元素能够尽量快地移动，从而降低运行的复杂度呢？

希尔排序的做法是先将元素进行分组，每次先在组内进行排序，尽量让元素可以在早期尽量多地移动。

比如还是上面的元素，我们第一次选择分组的跨度是5，一开始的跨度是数组长度的一半。我们可以参考上图，相同颜色的元素为一组。以其中的8和3为例，我们在组内进行插入排序之后，会使得3和8调换位置。对于元素3而言，它通过一次交换就移动到了数组的最前面。显然比依次移动要快得多。

组内进行排序之后，我们接着将跨度缩小一半，从5变成2，接着重复上述逻辑，得到：

最后，跨度设为1，总体进行插入排序，得到结果。由于我们之前已经调整了几次元素的位置，最后一次插入排序的交换元素的次数大大减小。

我们来尝试着写出代码：

void shell_sort(vector<int>& nums) {
    int n = nums.size();
    int h = n / 2;
    while (h > 0) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && nums[j] < nums[j-h]; j-=h) swap(nums[j], nums[j-h]);
        }
        h >>= 1;
    }
}

希尔排序的原理看起来复杂，但代码实现却很简单。不过这段代码虽然短，但想要写好可不容易，值得大家好好揣摩。

最后，聊一下关于算法的复杂度，关于希尔排序的复杂度的证明过程非常的复杂，因此书中也没有详细阐述，感兴趣的同学可以去搜索引擎去搜索一下相关内容。我保证它肯定比算法本身要难懂得多，大致上我们可以把希尔排序的复杂度理解成左右。

我们通过一个小小的优化，就减小了排序问题的复杂度，不得不说还是很神奇的。排序算法虽然看起来简单，但当中的内核以及原理其实一点都不简单，之后还有更多的内容在等待着大家，让我们一起期待吧。

好了，关于希尔排序就先聊到这里，感谢大家的阅读。

<END>

每日打卡赢积分兑换书籍入口