算法之美——希尔排序

1.概念

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

2.基本思想

最要的就第一步分组

(1).分组[设置间隔增量，一般通常设置为总长的一半]

(2).组内排序

(3).继续分组，以此类推，直至增量为1时，结束。

3.排序过程

图1

4.程序展示(python3)

图2

5.稳定性

虽然插入排序是稳定性，但是希尔排序在插入的时候是跳跃式插入，有可能破坏稳定性。

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

6.时间复杂度

O(n^(1.3—2))

扩展：希尔排序适合大规模无序数列，与普通插入排序相较，其效率是呈指数级提升。

图3是对总长为一万的无序数列排序，使用普通插入排序与希尔排序的对比。此数据来源于秒懂课堂。

图3

参考文献：

上述概念参考百度百科点击这里查看

有什么问题请留言，大家一起探讨学习😊😊😊。