图解算法---希尔排序（转载）

电玩女神 2023-06-13 09:07 83阅读 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]

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

[---]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTAzMDY4ZWRiZWYxNzdm?x-oss-process=image/format,png
[--- 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3A5LnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTAzMjRhN2FiNGIwYmE5?x-oss-process=image/format,png
[--- 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTAzNjBhMThiYjlkOWE0?x-oss-process=image/format,png
[--- 3]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTAyODQ4MDY3ZTYwYzU1?x-oss-process=image/format,png
[--- 4]: https://imgconvert.csdnimg.cn/aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA0MTYxOTVhMGE5Yjc2?x-oss-process=image/format,png
[--- 5]: https://imgconvert.csdnimg.cn/aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA0MTE3MzFjNGQ0ODZk?x-oss-process=image/format,png
[--- 6]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA2MjE4Mzg5ZjQ2ZTI0?x-oss-process=image/format,png
[--- 7]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA1ODRkOTY2MDRiNzAx?x-oss-process=image/format,png
[--- 8]: https://imgconvert.csdnimg.cn/aHR0cDovL3A5LnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA2MDVmMWFjYzY1NGM4?x-oss-process=image/format,png
[--- 9]: https://imgconvert.csdnimg.cn/aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA2MzI4OWM0ZjI4N2Ez?x-oss-process=image/format,png
[--- 10]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA2ODc2ZDFkYjk0Y2Y5?x-oss-process=image/format,png
[--- 11]: https://imgconvert.csdnimg.cn/aHR0cDovL3A5LnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA3NjFmN2YzMmRmNTI4?x-oss-process=image/format,png
[--- 12]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA4NzA3MjcwMjc4MmM1?x-oss-process=image/format,png
[--- 13]: https://imgconvert.csdnimg.cn/aHR0cDovL3A5LnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA5NDlhZjkwZGQ3NTY1?x-oss-process=image/format,png
[--- 14]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTA5NzE0MWQxZjI0Mjk2?x-oss-process=image/format,png
[--- 15]: https://imgconvert.csdnimg.cn/aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEwMTA3YjBhZWFlYzhl?x-oss-process=image/format,png
[--- 16]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEwMzY2M2Y5NDhlMTJi?x-oss-process=image/format,png
[--- 17]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEwNTJkODJjODAxYTZh?x-oss-process=image/format,png
[--- 18]: https://imgconvert.csdnimg.cn/aHR0cDovL3A5LnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTExMTQ4ZGZmZTI2MzM2?x-oss-process=image/format,png
[--- 19]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEyMjJmMTBmYWJmMGM4?x-oss-process=image/format,png
[--- 20]: https://imgconvert.csdnimg.cn/aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEyMzJhMjc3ODhjMTcw?x-oss-process=image/format,png
[--- 21]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEyMjkxMjcxYTQ0YjQ4?x-oss-process=image/format,png
[--- 22]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTE0MjMyZDQwMzc4Yjc4?x-oss-process=image/format,png
[--- 23]: https://imgconvert.csdnimg.cn/aHR0cDovL3A5LnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTEzMzQ5ODFmZGZhZjQx?x-oss-process=image/format,png
[--- 24]: https://imgconvert.csdnimg.cn/aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTE0MTEzYTI5MGJmZGE2?x-oss-process=image/format,png
[--- 25]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTE0ODRjM2E5Nzg0YWM5?x-oss-process=image/format,png
[--- 26]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTE0NjMzOWVhNmQ0N2Zj?x-oss-process=image/format,png
[--- 27]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTE1OTFjNTZhZWRiZTYw?x-oss-process=image/format,png
[--- 28]: https://imgconvert.csdnimg.cn/aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MjM3NjMzOTE1ODIzNjczN2MzZWE0?x-oss-process=image/format,png