Like Share Discussion Bookmark Smile

J.J. Huang   2020-03-09   排序演算法   瀏覽次數:

排序演算法 | 希爾排序

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

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

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

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

希爾排序演算法彩條:

範例說明

例如,假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我們以步長為5開始進行排序,我們可以通過將這列表放在有5行的表中來更好地描述演算法,這樣他們就應該看起來是這樣:

1
2
3
4
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然後我們對每行進行排序:

1
2
3
4
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
6
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之後變為:

1
2
3
4
5
6
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

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


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

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

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

實作範例(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@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));
}

結果:

1
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

那麼在上面的程序段中,數組長度為15,所以在第一輪,數組被分為了15 / 2 = 7個小組,然後分別對每個小組的元素進行遍歷。在第一輪中小組之間的元素間隔都為7,所以分成的小組數其實也就是元素之間的間隔。接著就可以對每個小組的元素進行比較,然後進行交換,接下來以此類推。


註:以上參考了
維基百科-希爾排序
演算法筆記
程式员必须掌握的核心算法有哪些?
程式员那些必须掌握的排序算法(上)
程式员那些必须掌握的排序算法(下)