實質(zhì)：插入排序的一種，先實現(xiàn)大步長的交換，再進行小步長的交換。

基本思想：維基百科：“希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）”。

實現(xiàn)方法：
選擇步長
按照選擇的步長對序列進行排序
縮短步長
返回步驟二繼續(xù)排序，直到步長為1

拓展：
Donald Shell最初建議步長選擇為n/2并且對步長取半直到步長達到1。雖然這樣取可以比O(n^2)類的算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的余地?？赡芟柵判蜃钪匾牡胤皆谟诋斢幂^小步長排序后，以前用的較大步長仍然是有序的。比如，如果一個數(shù)列以步長5進行了排序然后再以步長3進行排序，那么該數(shù)列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那么算法在迭代過程中會打亂以前的順序，那就不會以如此短的時間完成排序了。