希爾排序

算法思想

它是對插入插入排序的改進

搜索維基百科可知
希爾排序，也稱遞減增量排序算法

假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
，我們分別以步長為5，3，1進行排序（希爾排序最后的步長一定是1）

• 步長為5，我們可以得到如下數據，
  13 14 94 33 82
  25 59 94 65 23
  45 27 73 25 39
  10

• 然后 按照列排序
  10 14 73 25 23
  13 27 94 33 39
  25 59 94 65 82
  45

• 將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然后再以3為步長進行排序：
  10 14 13
  25 23 33
  27 25 59
  39 65 73
  45 94 82
  94
  -最后以1步長進行排序（此時就是簡單的插入排序了）。

代碼實現

public static void shellPass(Integer[] array, int d) {
    for (int i = d; i < array.length; i++) {
        int temp = array[i];
        int j = i - d;
        while (j >= 0 && array[j] > temp) {
            array[j + d] = array[j];
            j -= d;
        }
        array[j + d] = temp;
    }
}

public static void shellSort(Integer[] data) {
    int increment = 12;
    do {
        increment = increment / 3 + 1;
        shellPass(data, increment);
    } while (increment > 1);

}