排序算法4（希尔排序）

• • • 希尔排序核心机制
      • 希尔排序的C语言编程实现
      • 希尔排序中步长参数的选取方法

希尔排序原理

希尔排序作为对直接插入排序算法的一种优化形式，二者均归属于插入排序这一算法类别。

在上一节讲解 直接插入排序 的过程中，曾提及直接插入排序所具备的若干优势，其中尤为突出的是 当数据序列接近有序状态时，其运行效率较为理想 。

希尔排序的核心改进之处在于加速数据趋于有序的过程。

具体而言，如何实现数据的快速有序化？其实方法较为简单，即对原始数据实施 间隔式直接插入排序 。

如以下动画所示（可在参考链接中从头观看原始演示），首先以 Gap=10 对分组后的数据执行直接插入排序操作，随后采用 Gap=4 对分组数据进行一次直接插入排序，最终以 Gap=1 进行一次完整的直接插入排序。

可以简要归纳出以下几个方面：

（1） 因为直接插