反饋

Shell排序

希爾排序是一種插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又稱作縮小增量排序。Shell排序的執行時間依賴於增量序列。

中文名: Shell排序
別名: 縮小增量排序

類型: 一種插入排序算法
出自: D.L.Shell

Shell排序基本思想

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

該方法實質上是一種分組插入方法。

Shell排序算法分析

Shell排序增量序列

Shell排序的執行時間依賴於增量序列。

好的增量序列的共同特徵：

① 最後一個增量必須為1；

② 應該儘量避免序列中的值（尤其是相鄰的值）互為倍數的情況。

有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在n到1.6n之間。

Shell排序時間性能

希爾排序的時間性能優於直接插入排序的原因：

①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。

②當n值較小時，n和n^2的差別也較小，即直接插入排序的最好時間複雜度O(n)和最壞時間複雜度0(n^2)差別不大。

③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di-1作為距離排過序，使文件較接近於有序狀態，所以新的一趟排序過程也較快。

因此，希爾排序在效率上較直接插入排序有較大的改進。

Shell排序穩定性

希爾排序是不穩定的。參見上述實例，該例中兩個相同關鍵字49在排序前後的相對次序發生了變化。

Shell排序算法討論

Shell排序算法的時間複雜度分析比較複雜，實際所需的時間取決於各次排序時增量的個數和增量的取值。研究證明，若增量的取值比較合理，Shell排序算法的時間複雜度約為O（n（ldn）2）。由於Shell排序算法是按增量分組進行的排序，所以Shell排序算法是一種不穩定的排序算法。

Shell排序算法步驟

Step1 將n個元素個數列分為5個小組，在每個小組內按直接插入法排序；

step2 在第i步，分組個數取 di+1 =（di +1）/2 {9，5，3，2，1}；相臨兩組之間的對應元素進行比較，如果ai＞aj，則交換它們的位置；

Step3 當dK = 1的循環過程完成後，排序過程結束。

希爾排序舉例：設有字符數列"f d a c b e"，執行Shell排序：

Shell排序算法總結

下面幾個算法有研究價值

/*
*D.Shell最初的算法。
*/
int shellsortSh(int p[],int n)
{
    int op=0;
    int h,i,j,temp;
    for(h=n/2;h>0;h=h/2）{
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

shell排序算法C語言實現
void shellsort(int v[], int n){
    int gap, i, j, temp;
    for (gap = n / 2; gap > 0; gap /= 2){
        for (i = gap; i < n; i++){
            for (j = i - gap; j >= 0 && v[j]>v[j + gap];j-=gap){
                temp = v[j];
                v[j] = v[j + gap];
                v[j + gap] = temp;
            }
        }
    }
}

Lazarus-Frank 算法，1960 年發表。

/*
*原為在必要時加1使所有增量都為奇數，現修正為減1。
*/
int shellsortLF(int p[],int n)
{
    int op=0;
    int h,i,j,temp;
    for(h=n/2;h>0;h=h/2）{
        if(h%2==0)
        h--;
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Hibbard 算法、1963 年發表

/*
*1965年Papernov-Stasevich給出了數學證明。
*/
int shellsortHb(int p[],int n)
{
    int op=0;
    int h,i,j,temp;
    for(h=1;h<=n/4;h=h*2+1）；
    for(;h>0;h=(h-1）/2）{
        /*h=1,3,7,15,31...2^i-1*/
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Papernov-Stasevich 算法，1965年發表

int shellsortPS(int p[],int n)
{
    int op=0;
    int h,i,j,temp;
    for(h=2;h<=n/4;h=h*2-1）；
    for(;h>1;){
        h=(h==3）?1:(h+1）/2;
        /*h=1,3,5,9,17,33...2^i+1*/
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Knuth 算法，他建議在 n＜1000 時使用

int shellsortKn(int p[],int n)
{
    int op=0;
    int h,i,j,temp;
    for(h=1;h<=n/9;h=h*3+1）；
    for(;h>0;h=h/3）{
        /*h=1,4,13,40,121,364...3*h+1*/
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Pratt 算法、1971 年發表

/*
*原為h=2^p*3^q現修正為7^p*8^q。
*/
int shellsortPr(int p[],int n)
{
    int op=0;
    int h,i,j,t,temp;
    int incs[28]={
    262144,229376,200704,175616,153664,134456,
    117649,32768,28672,25088,21952,19208,16807,
    4096,3584,3136,2744,2401,512,448,392,343,
    64,56,49,8,7,1
    };
    for(t=0;t<28;t++){
        h=incs[t];
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Sedgewick 算法，1982 年發表

int shellsortSe82(int p[],int n)
{
    int op=0;
    int h,i,j,t,temp;
    for(t=1;t*t<=n/4;t+=t);
    for(h=n/4;t>0;t/=2,h=t*t-（3*t)/2+1）{
        /*h=1,8,23,77,281,1073,4193,16577,
        *65921,262913,1050113...4^i+3*2^(i-1）+1*/
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Gonnet 算法，發表於 1991 年

int shellsortGo(int p[],int n)
{
    int op=0;
    int h,i,j,temp;
    for(h=n;h>1;){
        h=(h<5）?1:(h*5-1）/11;
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Incerpj-Sedgewick 算法，1985 年發表。

int shellsortIS(int p[],int n)
{
    int op=0;
    int h,i,j,t,temp;
    int incs[16]={/*a1=3,a2=7,a3=16,a4=41,a5=101*/
    1391376,/*a1*a2*a3*a4*a5*/
    463792,/*a2*a3*a4*a5*/
    198768,/*a1*a3*a4*a5*/
    86961,/*a1*a2*a4*a5*/
    33936,/*a1*a2*a3*a5*/
    13776,/*a1*a2*a3*a4*/
    4592,/*a2*a3*a4*/
    1968,/*a1*a3*a4*/
    861,/*a1*a2*a4*/
    336,/*a1*a2*a3*/
    112,/*a2*a3*/
    48,/*a1*a3*/
    21,/*a1*a2*/
    7,/*a2*/
    3,/*a1*/
    1
    };
    for(t=0;t<16;t++){
        h=incs[t];
        for(i=h;i<n;i++){
            temp=p[i];
            for(j=i-h;j>=0&&p[j]>temp;j-=h){
                p[j+h]=p[j];
                op++;
            }
            p[j+h]=temp;
            op++;
        }
    }
    return op;
}

Shell排序的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：35次歷史版本
最近更新： thereforenay （2023-12-20）

1 基本思想
2 算法分析: 2.1 增量序列; 2.2 時間性能; 2.3 穩定性; 2.4 算法討論
3 算法步驟
4 算法總結