关于希尔排序算法

　　希尔排序是一种插入排序，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。
　　基本思想：
　　不断把待排序的对象分成若干个小组，对同一小组内的对象采用直接插入法排序，当完成了所有对象 都分在一个组内的排序后，排序过程结束。每次比较指定间距的两个数据项，若左边的值小于右边的值，则交换它们的位置。间距d按给定公式减少： di+1 =（di +1）/2 ，直到d等于1为止。D可以选取{9，5，3，2，1}。
　　算法步骤：
　　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排序算法的描述：
　　算法讨论：
　　Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排序时增量的个数和增 量的取值。研究证明，若增量的取值比较合理，Shell排序算法的时间复杂度约为O（n（ldn）2）。由于Shell排序算法是按增量分组进行的排序， 所以Shell排序算法是一种不稳定的排序算法。
　　shell排序算法总结
　　Latest Snippet Version: 1.01
　　/*
　　* Shell 排序算法在 1959 年由 D. Shell 发明。
　　* 也称为递减增量排序算法，各种实现在如何进行递减上有所不同。
　　* 不稳定，不需要辅助空间。
　　*/
　　/*
　　* 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 　　temp=p;
　　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 　　temp=p;
　　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 算法，1986 年发表。Knuth 推荐。
　　*/
　　int shellsortSe(int p[],int n)
　　{
　　int op=0;
　　int h,i,j,t,temp;
　　int incs[18] = {
　　1045505, 587521, 260609, 146305, 64769,
　　36289, 16001, 8929, 3905, 2161, 929,
　　505, 209, 109, 41, 19, 5, 1
　　};
　　/* if (i%2) h=8*pow(2,i)-6*pow(2,(i+1)/2)+1;
　　* else h=9*pow(2,i)-9*pow(2,i/2)+1; */
　　for (t=0; t<18; t++) {
　　h=incs[t];
　　if (h>n/3)
　　continue;
　　for (i=h; i 　　temp=p;
　　for (j=i-h; j>=0 && p[j]>temp; j-=h) {
　　p[j+h]=p[j];
　　op++;
　　}
　　p[j+h]=temp;
　　op++;
　　}
　　}
　　return op;
　　}
　　/*
　　* Tokuda(徳田尚之)算法。发表于 1992 年。
　　*/
　　int shellsortTo(int p[],int n)
　　{
　　int op=0;
　　int h,i,j,t,temp;
　　int incs[18] = {
　　1747331, 776591, 345152, 153401, 68178,
　　30301, 13467, 5985, 2660, 1182, 525,
　　233, 103, 46, 20, 9, 4, 1
　　};
　　/* h=ceil((9*pow(2.25,i)-4)/5) */
　　for (t=0; t<18; t++) {
　　h=incs[t];
　　if (h>n*4/9)
　　continue;
　　for (i=h; i 　　temp=p;
　　for (j=i-h; j>=0 && p[j]>temp; j-=h) {
　　p[j+h]=p[j];
　　op++;
　　}
　　p[j+h]=temp;
　　op++;
　　}
　　}
　　return op;
　　}
　　/*
　　* Ciura 算法。发表于 2001 年。性能卓越。
　　*/
　　int shellsortCi(int p[],int n)
　　{
　　int op=0;
　　int h,i,j,t,temp;
　　int incs[18] = {
　　2331004, 1036002, 460445, 204643, 90952,
　　40423, 17965, 7985, 3549, 1577, 701,
　　301, 132, 57, 23, 9, 4, 1
　　};
　　for (t=0; t<18; t++) {
　　h=incs[t];
　　if (h>n*4/9)
　　continue;
　　for (i=h; i 　　temp=p;
　　for (j=i-h; j>=0 && p[j]>temp; j-=h) {
　　p[j+h]=p[j];
　　op++;
　　}
　　p[j+h]=temp;
　　op++;
　　}
　　}
　　return op;
　　}
　　/*******************************************/
　　/* 下面几个算法有研究价值 */
　　/*******************************************/
　　/*
　　* 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 　　temp=p;
　　for (j=i-h; j>=0 && p[j]>temp; j-=h) {
　　p[j+h]=p[j];
　　op++;
　　}
　　p[j+h]=temp;
　　op++;
　　}
　　}
　　return op;
　　}
　　/*
　　* 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 　　temp=p;
　　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 　　temp=p;
　　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 　　temp=p;
　　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 　　temp=p;
　　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 　　temp=p;
　　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 　　temp=p;
　　for (j=i-h; j>=0 && p[j]>temp; j-=h) {
　　p[j+h]=p[j];
　　op++;
　　}
　　p[j+h]=temp;
　　op++;
　　}
　　}
　　return op;
　　}