希爾排序是一種插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又稱作縮小增量排序。Shell排序的執行時間依賴於增量序列。
基本介紹
- 中文名：Shell排序
- 類型：一種插入排序算法
- 出自：D.L.Shell
- 別名：縮小增量排序
基本思想,算法分析,增量序列的選擇,Shell排序的時間性能優於直接插入排序,穩定性,算法討論,算法步驟,算法總結,Hibbard 算法，1963 年發表。,Knuth 算法，他建議在 n<1000 時使用。,Pratt 算法，1971 年發表,Sedgewick 算法，1982 年發表,Gonnet 算法，發表於 1991 年。,
基本思想
先取一個小於n的整數d1作為第一個增量，把檔案的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重複上述的分組和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有記錄放在同一組中進行直接插入排序為止。
該方法實質上是一種分組插入方法。
算法分析
增量序列的選擇
Shell排序的執行時間依賴於增量序列。
好的增量序列的共同特徵：
① 最後一個增量必須為1；
② 應該儘量避免序列中的值(尤其是相鄰的值）互為倍數的情況。
有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在n到1.6n之間。
Shell排序的時間性能優於直接插入排序
希爾排序的時間性能優於直接插入排序的原因：
①當檔案初態基本有序時直接插入排序所需的比較和移動次數均較少。
②當n值較小時，n和n^2的差別也較小，即直接插入排序的最好時間複雜度O(n）和最壞時間複雜度0(n^2）差別不大。
③在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，後來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由於已經按di-1作為距離排過序，使檔案較接近於有序狀態，所以新的一趟排序過程也較快。
因此，希爾排序在效率上較直接插入排序有較大的改進。
穩定性
希爾排序是不穩定的。參見上述實例，該例中兩個相同關鍵字49在排序前後的相對次序發生了變化。
算法討論
Shell排序算法的時間複雜度分析比較複雜，實際所需的時間取決於各次排序時增量的個數和增量的取值。研究證明，若增量的取值比較合理，Shell排序算法的時間複雜度約為O（n（ldn）2）。由於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排序：
算法總結
下面幾個算法有研究價值
/**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;}