希爾排序(Shell Sort)演算法是插入排序(Insertion Sort)演算法的改良版。它解決了插入排序法一次只能把元素移動一個索引距離的問題,加入間距(gap)的概念來分批並分組完成插入排序法,有效提升原本插入排序法的速度。



希爾排序法(Shell Sort)

希爾排序法的概念

希爾排序法是基於插入排序法的演算法,如果您還不了解插入排序法的話,請先參考這篇文章:

https://magiclen.org/insertion-sort/

希爾排序法在插入排序法的基礎上添加了間距(gap)的概念,使得插入排序法可以分組執行,並且元素的移動距離可以大於一。希爾排序法會對序列由大至小,小則至1,來選擇應用在插入排序法上的間距,這樣一來就可以讓序列後端比較小的元素,在被使用前面幾次的大間距插入排序法排序之後,就先被移動到較前端的位置,使它們在最後的快速排序法中,不需要大老遠的從後端以一次一個索引距離的方式來移動到前端。

希爾排序法的過程

假設現在有個陣列資料,內容如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   69  81  30  38   9   2  47  61  32  79

要如何將它遞增排列呢?

如果在一開始我們選擇使用的間距是3的話,希爾排序法則會以以下的分組方式來執行快速排序法:

索引    0   1   2   3   4   5   6   7   8   9
數值   69          38          47          79
           81           9          61
               30           2          32

所以經過排序後,陣列內的元素分佈如下:

索引    0   1   2   3   4   5   6   7   8   9
數值   38          47          69          79
            9          61          81
                2         30          32

索引    0   1   2   3   4   5   6   7   8   9
數值   38   9   2  47  61  30  69  81  32  79

如果在下一次我們選擇使用的間距是2的話,希爾排序法則會以以下的分組方式來執行快速排序法:

索引    0   1   2   3   4   5   6   7   8   9
數值   38       2      61      69      32
            9      47      30      81      79

經過排序後,陣列內的元素分佈如下:

索引    0   1   2   3   4   5   6   7   8   9
數值    2      32      38      61      69
            9      30      47      79      81

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  32  30  38  47  61  79  69  81

最後使用間距1,來完成排序:

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

shell-sort

希爾排序法的程式實作

希爾排序法的複雜度

以#{{n}}#來表示要排序的資料筆數。

項目備註
最差時間複雜度#{{O(n^2)}}#
#{{O(n \log^2 n)}}#
使用最差的間距。
使用Marcin Ciura的間距值。
最佳時間複雜度#{{O(n \log n)}}#
#{{O(n \log^2 n)}}#
使用最佳的間距。
使用Marcin Ciura的間距值。
平均時間複雜度?
#{{O(n \log^2 n)}}#
根據間距值來決定。
使用Marcin Ciura的間距值。
額外最差空間複雜度#{{O(1)}}#
是否穩定如果是普通的插入排序法則是穩定的。