【数据结构】排序——希尔排序

前言 本篇博客，我们继续介绍一种排序——希尔排序，上篇博客我们说了插入排序，了解了插入排序，那希尔排序又是什么那，我们一起来看看 💓 个人主页：小张同学zkf ⏩ 文章专栏：数据结构 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章

1.希尔排序概念

由于希尔排序需要用到插入排序的思想，我们先来回顾一遍插入排序的实现动态图

插入排序的代码

希尔排序法又称 缩小增量法 。希尔排序法的基本思想是： 先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达 =1 时，所有记录在统一组内排好序 。

也就是说希尔排序是一个逐渐有序的过程，最后一次排序就是插入排序

正如概念所说我们现将一写数据分好组，在同一组内先进行插入排序，然后在其他组重复插入排序，如下图

这个gap就是组间距，由图可知最后当gap为1时，其排序就是一个插入排序

希尔排序的特性总结： 1. 希尔排序是对直接插入排序的优化。 2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

《数据结构 - 用面相对象方法与 C++ 描述》 --- 殷人昆

4. 稳定性：不稳定

2.实现希尔排序

了解了希尔排序的特点，那么如何实现希尔排序那

我们先给出以下数据，给他们排序

9 1 2 5 7 4 8 6 3 5

如何利用希尔排序给这一数据排序

我们先假设组间距gap为3

我们先把组间距为3的组，把这些组先进行插入排序

先看红线连的一组

9 5 8 5

通过插入排序，得

5 5 8 9

再看绿线

1 7 6

插入排序得

1 6 7

最后看紫线

2 4 3

插入排序得

2 3 4

所以最终数据就变成

5 1 2 5 6 3 8 7 4 9

我们可以观察到，通过一次预排序，观察到的结果

注意此时数据还没有有序，但我们先可以把此部分代码写出来，总之，代码整体上就是插入排序，只不过分组来插入。

这个是一组一组走的代码

这个是多组并着走的代码

接下来我们就要变化gap，我们要记住一点，gap最后结果一定为一（此刻数据为有序），我们一般每次将gap自除3（比较合理的一种，官方并没有明确），由于最后确保gap为1，我们应该gap除3再加一。

所以gap的变化顺序，我们可以通用的将gap初始值设为数据数量，然后依次除三再加一，直到gap为1，跳出循环，此刻数据就变有序

最终希尔排序的代码就是

3.希尔排序的时间复杂度

希尔排序的时间复杂度我们记住是O（n^1.3）

至于怎么算的，小编数学不太好哈哈哈，就说一下大致的过程。

我们先看gap每次除三（1省略），每次排序最坏的情况相当于排了数据数量*组数（n/3）

最后一趟组间距为1，相当于排了n次，由此可见在排序过程中，次数逐渐升高达到最高点再逐渐降低，再根据概率轮相关知识，可得出O（n^1.3）

结束语 希尔排序总结完，下一个排序就是我们大家最熟悉的快速排序，快速排序有好几种实现方法，希尔排序还有不明白的可以评论区说。 OK，本篇博客结束，感谢观看！！！