前言

本篇博客，我们继续介绍一种排序——希尔排序，上篇博客我们说了插入排序，了解了插入排序，那希尔排序又是什么那，我们一起来看看

💓 个人主页：小张同学zkf

⏩ 文章专栏：数据结构

若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

目录

1.希尔排序概念

 2.实现希尔排序

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

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

插入排序的代码

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

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

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

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

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，跳出循环，此刻数据就变有序

最终希尔排序的代码就是

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

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

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

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

结束语 

希尔排序总结完，下一个排序就是我们大家最熟悉的快速排序，快速排序有好几种实现方法，希尔排序还有不明白的可以评论区说。

OK，本篇博客结束，感谢观看！！！