10.3.3　希尔排序

希尔排序（Shell’s Sort）也称为缩小排序算法，是插入排序算法的一种更高效改进算法，该方法由DL.Shell于1959年提出而得名。其实现思路为：分组增量实现插入排序算法，第一轮分组插入排序结束后增量缩小，进入第二轮分组，依次类推，一直到增量为1后，完成最后一轮插入排序操作。

在实际操作时，第一轮增量一般采用队列元素个数的一半作为第一次增量操作d1=n//2（n为奇数时，d1=n//2+1）；从第二轮开始每轮增量减1；一直到增量减少到1为止。

其实现原理举例如图10.6所示。