希尔排序--简单易懂图解

朴灿烈づ我的快乐病毒、 2023-05-31 02:57 10阅读 0赞

# 图解算法---希尔排序 #

![图解算法---希尔排序][---]

![图解算法---希尔排序][--- 1]

前情回顾：直接插入排序（对插入排序不熟悉的建议先阅读此文）

一天，一尘拿着扑克自己在那玩，刚被师傅看见了

![图解算法---希尔排序][--- 2]

![图解算法---希尔排序][--- 3]

![图解算法---希尔排序][--- 4]

首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高

![图解算法---希尔排序][--- 5]

![图解算法---希尔排序][--- 6]

可以看出，他是按下标相隔距离为4分的组，也就是说把下标相差4的分到一组，比如这个例子中a\[0\]与a\[4\]是一组、a\[1\]与a\[5\]是一组...，这里的差值（距离）被称为增量

![图解算法---希尔排序][--- 7]

每个分组进行插入排序后，各个分组就变成了有序的了（整体不一定有序）

![图解算法---希尔排序][--- 8]

此时，整个数组变的部分有序了（有序程度可能不是很高）

![图解算法---希尔排序][--- 9]

然后缩小增量为上个增量的一半:2，继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比高

![图解算法---希尔排序][--- 10]

同理对每个分组进行排序（插入排序），使其每个分组各自有序

![图解算法---希尔排序][--- 11]

最后设置增量为上一个增量的一半：1，则整个数组被分为一组，此时，整个数组已经接近有序了，插入排序效率高

![图解算法---希尔排序][--- 12]

同理，对这仅有的一组数据进行排序，排序完成

![图解算法---希尔排序][--- 13]

![图解算法---希尔排序][--- 14]

![图解算法---希尔排序][--- 15]

![图解算法---希尔排序][--- 16]

![图解算法---希尔排序][--- 17]

随后一尘写出了插入arr\[i\]到所在组正确位置的代码（insertI）

![图解算法---希尔排序][--- 18]

![图解算法---希尔排序][--- 19]

![图解算法---希尔排序][--- 20]

![图解算法---希尔排序][--- 21]

![图解算法---希尔排序][--- 22]

希尔排序的复杂度和增量序列是相关的

\{1,2,4,8,...\}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)

Hibbard提出了另一个增量序列\{1,3,7，...,2^k-1\}，这种序列的时间复杂度(最坏情形)为O(n^1.5)

Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是\{1,5,19,41,109,...\}

![图解算法---希尔排序][--- 23]

![图解算法---希尔排序][--- 24]

![图解算法---希尔排序][--- 25]

![图解算法---希尔排序][--- 26]

![图解算法---希尔排序][--- 27]

![图解算法---希尔排序][--- 28]

说完，一尘继续玩起了扑克。

[---]: /images/20230531/5a25278773c1460180786b6624d8e551.png
[--- 1]: /images/20230531/e8c6b7ab015a4838996830d9fe506f65.png
[--- 2]: /images/20230531/91ee7bf24613492f8cfecf91dac17a99.png
[--- 3]: /images/20230531/20dcf84df7d342eaa1f2c0fdfb54a46e.png
[--- 4]: /images/20230531/293084c4f1c649889ab12d85e137564d.png
[--- 5]: /images/20230531/23c28f9c88024dc9aaae457e14636549.png
[--- 6]: /images/20230531/3d81a9df539a4882ba0f91ba0f72c822.png
[--- 7]: /images/20230531/a7704ab448054e939477169f119e965a.png
[--- 8]: /images/20230531/06c20ad33f6b4bf99de85c7467df42be.png
[--- 9]: /images/20230531/7f6b7bb662b145108e9a7cb079b09816.png
[--- 10]: /images/20230531/55620fd9d5494b8cb9db2c02dc21ac3c.png
[--- 11]: /images/20230531/8bff01c4445944fabbff828c1fb68859.png
[--- 12]: /images/20230531/f46a8025983a4a1e92411300fff50eeb.png
[--- 13]: /images/20230531/eb4b7a1cc324439c9bfd9a9b6a5b312f.png
[--- 14]: /images/20230531/9497af7ad32a4c1899b2a40f93105770.png
[--- 15]: /images/20230531/255fd4d32c1544838278a0200ce70eb4.png
[--- 16]: /images/20230531/1a3a1b9f298a42c0a4b0fd285ffcaee9.png
[--- 17]: /images/20230531/25bee24a45be4ecd916a359856a8bc65.png
[--- 18]: /images/20230531/807e20b389024a6b9a19b3a28634207d.png
[--- 19]: /images/20230531/66c93f3b1b6543bd8fe716fc2b4484c9.png
[--- 20]: /images/20230531/d9adc533aa174244a6a67c2846f969c5.png
[--- 21]: /images/20230531/a713557f89954d86a2e9b82d5ec0779c.png
[--- 22]: /images/20230531/4cab1b0993824e3b8951a94da72fcd6c.png
[--- 23]: /images/20230531/820f79f514c741969f2a38ef35a64483.png
[--- 24]: /images/20230531/fe3338a934f24b8fbad962d4136beb44.png
[--- 25]: /images/20230531/cac7288f967c4c7eac76a33eb58ae3d0.png
[--- 26]: /images/20230531/693afeb99dcc42ef8a2e8a5905510379.png
[--- 27]: /images/20230531/288e4e331ba845cf8774f25a2144c529.png
[--- 28]: /images/20230531/cfbfe74c463047bf8814616c36b6ad7f.png