希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进
希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名
它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止

过程

希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2…1} 来表示。

算法实现

算法性能分析

总结