在前面已經對冒泡排序、直接插入排序做了說明分析（具體詳情可點擊下方的鏈接查看），本篇將對希爾排序進行相關說明分析。
排序算法系列目錄說明
冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
希爾排序（Shell Sort）
選擇排序（Selection Sort）
快速排序（Quick Sort）
歸併排序（Merge Sort）
堆排序（Heap Sort）
計數排序（Counting Sort）
桶排序（Bucket Sort）
基數排序（Radix Sort）
希爾排序（Shell Sort）
希爾排序的實質就是分組插入排序，該方法又稱遞減增量排序算法，因DL．Shell於1959年提出而得名。希爾排序是非穩定的排序算法。
在上一篇《算法：排序算法之插入排序》中優化方案中就有提到過使用希爾排序進行改進。希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率
但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位
1. 基本思想
先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。
因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。
2. 實現邏輯
先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。
所有距離為d1的倍數的記錄放在同一個組中，在各組內進行直接插入排序。
取第二個增量d2<d1重複上述的分組和排序，
直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
3. 動圖演示
希爾排序演示
具體我們以一組數字來說操作說明：
希爾排序示例圖
假設有一組｛9, 1, 2, 5, 7, 4, 8, 6, 3, 5｝無需序列。
第一趟排序：
設 gap1 = N / 2 = 5，即相隔距離為 5 的元素組成一組，可以分為 5 組。接下來，按照直接插入排序的方法對每個組進行排序。
第二趟排序：
將上次的 gap 縮小一半，即 gap2 = gap1 / 2 = 2 (取整數)。這樣每相隔距離為 2 的元素組成一組，可以分為 2 組。按照直接插入排序的方法對每個組進行排序。
第三趟排序：
再次把 gap 縮小一半，即gap3 = gap2 / 2 = 1。 這樣相隔距離為 1 的元素組成一組，即只有一組。按照直接插入排序的方法對每個組進行排序。此時，排序已經結束。
注：需要注意一下的是，圖中有兩個相等數值的元素5和5。我們可以清楚的看到，在排序過程中，兩個元素位置交換了。
4. 性能分析
平均時間複雜度：O(Nlog2N)
最佳時間複雜度：
最差時間複雜度：O(N^2)
空間複雜度：O(1)
穩定性：穩定
複雜性：較複雜
希爾排序的效率取決於增量值gap的選取，時間複雜度並不是一個定值。
開始時，gap取值較大，子序列中的元素較少，排序速度快，克服了直接插入排序的缺點；其次，gap值逐漸變小後，雖然子序列的元素逐漸變多，但大多元素已基本有序，所以繼承了直接插入排序的優點，能以近線性的速度排好序。
最優的空間複雜度為開始元素已排序，則空間複雜度為 0；最差的空間複雜度為開始元素為逆排序，則空間複雜度為 O(N);平均的空間複雜度為O(1)希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化。比如上面的例子中希爾排序中相等數據5就交換了位置，所以希爾排序是不穩定的算法。
5. 代碼實現
C版本：
希爾排序（C版本實現）
C++版本：
希爾排序（C++實現）
Java版本：
希爾排序（Java實現）
6. 重點說明(步( 摘錄自wiki百科)
(6.1) 步長序列
步長的選擇是希爾排序的重要部分。只要最終步長為1任何步長序列都可以工作。算法最開始以一定的步長進行排序。然後會繼續以一定步長進行排序，最終算法以步長為1進行排序。當步長為1時，算法變為插入排序，這就保證了數據一定會被排序。
作者最初的建議是折半再折半知道最後的步長為1<也就是插入排序>,雖然這樣取可以比O(n2)類的算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的餘地。可能希爾排序最重要的地方在於當用較小步長排序後，以前用的較大步長仍然是有序的。比如, 如果一個數列以步長5進行了排序然後再以步長3進行排序，那麼該數列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那麼算法在迭代過程中會打亂以前的順序，那就不會以如此短的時間完成排序了。
(6.2) 常見步長序列
①步長序列：n/2i
最壞情況複雜度：O(n2)
②步長序列：2k-1
最壞情況複雜度：O(n3/2)
③步長序列：2i3j
最壞情況複雜度：O(nlog2n)
注意：頭條裡面無法顯示特殊符號，步長序列中i、k-1，j等都是右上標符號。
已知的最好步長序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，該序列的項來自9 x 4i - 9 x 2i + 1 和 2i+2 x (2i+2 -3)這兩個算式。(注意：頭條裡面無法顯示特殊符號，兩個公式中i，j等都是右上標符號)
總結
希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能，交換不相鄰的元素以對數組的局部進行排序，最終用插入排序將局部有序的數組排序。
希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴於增量因子序列d的選取，特定情況下可以準確估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：增量因子中除1外沒有公因子，且最後一個增量因子必須為1。希爾排序方法是一個不穩定的排序方法。
源碼地址：https://github.com/7-sevens/algorithm
想要獲取更多精品技術乾貨，歡迎關注微信公眾號：開發者小黑屋