希尔排序是一种插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。
基本介绍
- 中文名：Shell排序
- 类型：一种插入排序算法
- 出自：D.L.Shell
- 别名：缩小增量排序
基本思想
先取一个小于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;}
