[演算法] 希爾排序法 Shell Sort

　　希爾排序法 (Shell Sort)，由Donald Shell 於1959年發明最初版本，這也是此排序法的名稱由來，另外，由於操作方式，又被稱作增量遞減排序排序法 (diminishing increment sort)，是插入排序法的一種改進版本。

　　原始的插入排序法在插隊的時候需要一個一個比較和交換(或賦值)才能移動到正確位置，希爾排序認為如果一次移動長一點的距離，可以更快完成，例如某序列的最大值在其中一端點，插入排序法可能需要經過 n - 1次的比較和交換才能到另外一點，而若一次檢查1/4 序列長度，只要比較3次就可以了。所以希爾排序法利用不同的增量（步進）進行排序，在逐漸遞減增量，值到增量為１時回復到插入排序法，此時整個序列已經接近排序完成，所以可以以接近O(n)的速度排序完成。

　　希爾排序法最重要的就是決定增量遞減的方式，不同的增量方式可以決定最糟狀況下的複雜度，從O(n^2)、O(nlog^2n) 到 O(n^1.5)，詳細可以參考英文版的 Wiki，內有不同增量的時間複雜度。在序列不大時甚至有可能比快速排序法快一些。

複雜度：

• 時間： 最佳 O(n) 最差 O(n^1.5) [增量遞減方式為 3*n+1]
• 空間： O(n), O(1) 輔助

步驟：

1. 依照不同的方式先決定最大的增量(步進)值 A。
2. 以 A 為步進做插入排序法。
3. 依不同方式遞減 A 的值。
4. 重複步驟2. 3. 直到 A 小於 1 (A為1時是標準差入排序法)。
5. 完成排序。

Java 簡單實現：

 
/** 增量遞減方式為 3*n+1 */
public ShellSort {
     public void sort(int[] array) {
          int step = 1;

          // 決定最大增量
          while(step <= array.length/3) {
              step = 3 * step + 1;
          }
          
          while(step > 0) {
               // 進行插入排序法
               for(int i = step; i < array.length; i += step) {
                    int target = array[i];
                    int j = i;
                    while((j > 0) && (array[j - 1] > target)) {
                         array[j - 1] = array[j];
                         j--;
                    }
                    array[j] = target;
               }

               //遞減增量 
               step = (step - 1) / 3;
          }
     }
}

範例：
　　以 Wiki 的例子來舉例，有一序列為 [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，若決定增量為 5, 3, 1，則排序方式會如下：

原始數列，先用5個一列排好比較好理解。

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

以5為增量做插入排序法，可以看到每行都排列好了。

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

 換成3個排一列

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

以3為增量作為排序後

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最後再以1為增量，也就是進行一般的插入排序法做最後一次排列 (應該是直的，但省空間就橫放囉)

10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94

排序完成

10 13 14 23 25 25 27 33 39 45 59 65 73 82 94 94

 
範例影片：

參考資料：

1.  Wiki 希爾排序法
2. 英文 Wiki Shellsort