浙江大學-數據結構-希爾排序-9.2.1

03-06

希爾排序(by Donald Shell)

基本思路就是利用了插入排序的簡單，同時呢，它要克服插入排序每次只交換相鄰兩個元素的缺點，那要理解這個shell sort,我們先來舉個例子。

假設這是我們給定的一個數組，shell sort第一步要做的是我先做一個5間隔的排序，就是我考慮這個序列裡面的一個子序列，這個子序列的元素呢，是每隔5個來選取的，也就是說，我先選了第一個元素，然後相隔4個元素，第5個元素，然後再相隔4個元素，第5個元素，

我用插入排序對這個子序列，這3個數字做一個插入排序，排序以後的結果呢，是放在它們相應的位置，然後繼續考慮的是下面的一個5間隔的子序列，就是94，17，75

以此類推，考慮11，95，15，最後是96和28，

然後12和58

這就是5間隔排序以後的效果

在5間隔排序完成了以後呢，他把這個數字稍微變少一點，變成3，我要做一個3間隔的排序，在5間隔排序結果的基礎上，每隔3個取一個，這是一個3間隔排序

下一趟

再下一趟

這是一個3間隔排序的結果，我們會看到序列情況有了非常明顯的改善，當然最後我要保證這個序列有序的話，最後我還是得做1間隔的，徹底的插入排序，但是當我們最後在做1間隔的原始插入排序之前，我們發現3間隔的序列已經基本有序了，也就是大部分的逆序對已經在前面的兩趟排序裡面被消掉了，所以它的主要思想就是我先要定義一個增量序列，也就是我現在隨便定義了一個5，3，1，你也可以定義你自己的數字，但是無論如何這個序列它是遞減的，遞減到最小的那個，最後一步必須是1間隔的，定義這個增量序列以後，我們對每一個增量進行增量間隔的排序，

這個k是從M開始，一直減到1為止，那在這裡頭呢，有一個很重要的性質，我們必須要觀察到，就是當我對這個序列先進行了5間隔的排序，然後又進行了3間隔的排序，問題是3間隔排序以後，這個3間隔排序的序列還是5間隔有序的嗎？我們來看一下，在3間隔排序以後，我們看到28，隔4個，41，再隔4個，81，那麼28，41，81，它們仍然是有序的，然後再看12，58和96也是有序的，仔細檢查一遍，你會發現，3間隔有序的序列，還保持了前面5間隔有序的性質，也就是說更小間隔的排序，沒有把上一步的結果變壞，這是一個非常重要的性質，否則的話，這個shell排序就不好用了，我們用文藝一點的說法，就是下圖注意裡面的注釋

那看上去希爾排序是一個非常簡單的演算法，原始的希爾排序呢，也的確是非常簡單的，它的增量序列是怎麼選的呢？

一開始取一個N/2,然後每次把這個增量除以2，每次減半，每次減半，最後減到1為止，所以shell排序原始的演算法寫起來是非常簡單的，就是外面套一個大循環，是關於增量的，這是一個希爾的增量序列，它從N/2開始，一直到1為止，每次除以2

在這個大for循環的內部，它執行的就是一個非常直接的插入排序，你還記得原始的插入排序嗎？原始的插入排序，

假設第0張牌已經在我們手裡，我們每次是從第一張牌開始摸，那在這(就是指for(P=D; P<N; P++))因為間隔了D個距離，所以我們假設第0張牌在我手裡，我下一張牌是從第D張牌開始摸，也就是說把原來的插入排序里的1全部換成D就可以了，所以這就是一個非常簡單的shell排序的偽代碼，但是，一個很壞的消息告訴我們，最壞情況下，shell排序的時間複雜度是 $Theta(N^2)$ , $Theta$ 是什麼意思大家還記得嗎？我們說 $O$ 是一個上界，它有可能達不到那個上界， $Omega$ 是一個下界，而 $Theta$ 既是上界又是下界，也就是說它的增長速度真正的是跟 $N^2$ 一樣快的，這是一個非常壞的消息

到底什麼地方出了問題呢？我們再來看一個壞的例子，假設這是我們的初始序列，如果用shell的增量序列我們會一開始怎麼做呢？這一共有16個數字，

我們一開始就做8間隔的排序，8間隔的排序我們就從1開始，然後往後數7個數字，就是排1和5，發現本來就是有序的，什麼都不用動，然後下一個，就是9和13，也是有序的，2和6，還是有序的，10和14還是有序的，繼續往後看，就會發現，我做了一個8間隔的排序，結果哪個元素都沒有動，大家保持原樣的走下來了，下一步我要做4間隔的，結果還是全部都是有序的。

結果這趟又白跑了，2間隔的排序，你應該猜到結果了，還是什麼都沒幹，最後要達到有序，還是得靠我們1間隔的排序。

所以這其實是一個讓人非常囧的情況，就是前面我白做了3趟排序，然後最後還是跟原始的插入排序一樣，還不如一開始我就直接做原始的插入排序，那到底什麼地方出了問題呢？我們通過仔細的分析

會發現因為它的增量元素不互質，8是4的倍數，4是2的倍數，2是1的倍數，那麼小的增量就有可能在後面的排序裡面根本不起作用，那為了克服這個問題呢，有更多的學者提出了更多的增量序列，比如說Hibbard增量序列，它把每一步的增量定義成 $2^k-1$ ,這個增量序列的好處呢，是保證了相鄰的元素是互質的，什麼是互質，也就是相鄰的元素之間沒有公因子，Shell排序用Hibbard增量序列呢它的情況會稍微變好一點，

另外還有一個猜想，到現在為止都沒有人能夠證明的,Hibbard增量帶來的平均時間複雜度可能是 $O(N^{5/4})$

shell排序呢，從實際運用的角度來講，如果你要排序的元素它的數量是幾萬，這個數量級的，那麼用shell排序加上Sedgewick增量序列的話，這個效果是比較好的，shell排序就給我們大家一個很好的例子，你就看到一個演算法，它會是如此的簡單，但是呢，關於它的複雜度分析，是非常非常的難。