实质：插入排序的一种，先实现大步长的交换，再进行小步长的交换。
基本思想：维基百科：“希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）”。
实现方法：
选择步长
按照选择的步长对序列进行排序
缩短步长
返回步骤二继续排序，直到步长为1
拓展：
Donald Shell最初建议步长选择为n/2并且对步长取半直到步长达到1。虽然这样取可以比O(n^2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。
