閱讀764 返回首頁    go 微軟 go windows

排序算法係列之希爾排序

算法排序之希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種高速而穩定的改進版本。 

基本思想

   先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

希爾排序的時間性能優於直接插入排序的原因：
　　①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。
　　②當n值較小時，n和n2的差別也較小，即直接插入排序的最好時間複雜度O(n)和最壞時間複雜度0(n2)差別不大。
　　③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di-1作為距離排過序，使文件較接近於有序狀態，所以新的一趟排序過程也較快。
    　因此，希爾排序在效率上較直接插人排序有較大的改進。

步長選擇

Donald Shell 最初建議步長選擇為\frac{n}{2}並且對步長取半直到步長達到 1。雖然這樣取可以比\mathcal{O}(n^2)類的算法（插入排序）更好，但這樣仍然有減少平均時間和最差時間的餘地。 可能希爾排序最重要的地方在於當用較小步長排序後，以前用的較大步長仍然是有序的。比如，如果一個數列以步長5進行了排序然後再以步長3進行排序，那麼該數列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那麼算法在迭代過程中會打亂以前的順序，那就不會以如此短的時間完成排序了。

步長串行 最壞情況下複雜度
{n/2^i} \mathcal{O}(n^2)
2^k - 1 \mathcal{O}(n^{3/2})
2^i 3^j \mathcal{O}( n\log^2 n )

已知的最好步長串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，該串行的項來自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 這兩個算式.這項研究也表明“比較在希爾排序中是最主要的操作，而不是交換。”用這樣步長串行的希爾排序比插入排序和堆排序都要快，甚至在小數組中比快速排序還快，但是在涉及大量數據時希爾排序還是比快速排序慢。

另一個在大數組中表現優異的步長串行是(斐波那契數列除去0和1將剩餘的數以黃金分區比的兩倍的冪進行運算得到的數列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）

希爾排序動畫模擬以及動態圖演示

動畫演示：

假設待排序文件有10個記錄，其關鍵字分別是： 49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次為： 5，3，1
排序過程如【動畫模擬演示】

動態圖：

 Step-by-step visualisation of Shellsort

偽碼實現

input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:    
    for i = inc .. n − 1 do:        
        temp ← a[i]        
        j ← i        
        while j ≥ inc and a[j − inc] > temp do:            
            a[j] ← a[j − inc]            
            j ← j − inc        
        a[j] ← temp    
    inc ← round(inc / 2.2)

算法C語言實現

/**
 * 希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長
 * 最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了,步長很小,插
 * 入排序對於有序的序列效率很高。所以，希爾排序的時間複雜度會比o(n^2)好一些!
 * 希爾排序時間複雜度為O(nlog(n)) ~ O(n ^ 2)
 */

#include <stdio.h>

void shell_sort(int array[], int n)
{
    // increment為步長
    int tmp, i, j, increment;

    for(increment = n / 2; increment > 0; increment /= 2)
    {
        //下麵為插入排序，最壞時間複雜度為O（n^2）！
        for(i = increment; i < n; ++i)
        {
            tmp = array[i];

            for(j = i; j > 0 && tmp < array[j - increment]; j -= increment)
            {
                array[j] = array[j - increment];
            }
            array[j] = tmp;
        }
    }
}

測試main函數

int main()
{
    int array[] = {34，25，56，1，-1，-45};
    shell_sort(array, 6);
    for(int i = 0; i < 6; ++i)
        printf("%d ", array[i]);
    return 0;
}



最後更新：2017-04-03 20:19:55

  上一篇：go Eclipse 集成 Araxis Merge 作為比較和合並GUI工具的配置
  下一篇：go servlet、struts1和struts2的線程安全問題