排序演算法 | 希爾排序

希爾排序（Shellsort），也稱遞減增量排序演算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序演算法。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率。
但插入排序一般來說是低效的，因為插入排序每次只能將資料移動一位。

以23, 10, 4, 1的步長序列進行希爾排序：

希爾排序演算法彩條：

範例說明

例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有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為步長進行排序：

排序之後變為：

最後以1步長進行排序（此時就是簡單的插入排序了）。

傳統的插入排序算法在某些場景中存在著一些問題，例如[2，3，4，5，1]這樣的一個數組，當我們對其進行插入排序的時候，發現要插入的數字是1，而要想將1插入到最前面，需要經過四個步驟，分別將5、4、3、2後移。所以得出結論：如果較小的數是我們需要進行插入的數，那效率就會比較低。鑑於這種場景的缺陷，希爾排序誕生了，它是插入排序的一種更高效的版本。

先看看希爾排序的概念：
希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因D.L.Shell於1959年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。

動畫如果沒有看懂，我這裡再貼幾張靜態圖：

實作範例(Java)

@Test
public void ShellSort() {
    int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 對數組元素進行分組
        for (int i = gap; i < arr.length; i++) {
            // 遍歷各組中的元素
            for (int j = i - gap; j >= 0; j -= gap) {
                // 交換元素
                if (arr[j] > arr[j + gap]) {
                    int temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
    }
 
    System.out.println(Arrays.toString(arr));
}