排序的故事--SHELL排序

     SHELL是一种不需要辅助空间不稳定的排序法，在传统的教科书里面，SHELL排序法都是直接引用D.L.Shell在他1969年的原著《A High-Speed Sorting Procedure》中的办法：再要排序的数组中先把间隔为n/2的元素排好，然后把间隔为n/(2^2)的元素排好，再排间隔为n/(2^3)，n/(2^4)，... ，4，2，1的元素，最后就是一个依顺序排序好的结果。C程序如下：

void sort(int x[], int n)
{
       int gap;
       int i, j, temp;
       while(gap>0)
       {
            for (i=gap; i
                for (j=i-gap; j>=0 && x[j]>x[j+gap]; j-= gap) {
                     temp = x[j];
                     x[j] = x[j+gap];
                     x[j+gap] = temp;
                }
                gap = gap/2;
       }
}

      但是D.Kunth的著作中把早期的研究与他的发现作了一个总结，他指出用(2^j)-1，(2^j)-1的间隔进行排序分别是Hibbard、Papernovn与Stasevich的想法，而间隔数((3^j)-1)/2则是在他的书中首度出现的，把比较次数加快到与n^1.5成正比。
      D.Knuth很早就发现如何用((3^j)-1)/2的方式，亦即1，4，13，... ，这样的方法会比Shell原来的方法好一些。换言之，如果有n个元素，就得找出满足((3^j)-1)/2       后来就是青出于蓝而胜于蓝的故事，他的一名学生Robert Sedgewick把间隔数定为：4^(j+1)+3*(2^j)+1，于是把比较次数加快到了与n^(4/3)成正比，虽然1.5只比1.33多不了多少，但是这种科学家的精神我还是很佩服的。当然了还有好多关于间隔数如何选取的方法，这里就不一一介绍了。下面我们就以Robert Sedgewick的算法为例进行研究...
      由于4^(j+1)+3*(2^j)+1是需要排序的元素之间的间隔，因此它不能大于所有的元素的个数n，所以j必须满足下式：
               4^(j+1)+3*(2^j)+1 <= n
      把 4^(j+1)改写为4*(4^j)=4*[(2^j)]^2带回上式，就有：
               4*[(2^j)]^2 + 3*(2^j) + (1-n) <= 0
      把2^j用X换掉，于是就有：
               4*(X^2) + 3*X + (1-n) <= 0
      通过解方程和函数的特性(开口向上的抛物线)于是就可以求出j的最大值为：log[(-3+(16n-7)^1/2)/8]
      在程序中，可以用上面求出的j算出一个2^j，代入 4*[(2^j)]^2 + 3*(2^j) + 1，以求出的间隔值进行排序接着把2^j除以2，在代入4*[(2^j)]^2 + 3*(2^j) + 1得到一个新间隔值进行排序...一直到间隔为1时元素就排好顺序了，整个排序就大功告成了！

#include  <math.h></math.h>
#include  <stdio.h></stdio.h>
#include  <stdlib.h></stdlib.h>
#define   EQN(x) ((4*x+3)*x+1)

void  sort(int x[], int n)
{
       int  gap;
       int  power2;
       int  i, j, temp;
       power2 = log((-3.0 + sqrt(16.0*n-7.0))/8.0)/log(2.0);
       power2 = 1 << (power2 + 1);
       do
       {
             power2 >>= 1;
             gap = EQN(power2);
             for (i = gap; i < n; i++)
                  for (j=i-gap; j>=0 && x[j] > x[j+gap]; j -= gap)
                  {
                       temp = x[j];
                       x[j] = x[j+gap];
                       x[j+gap] = temp;
                  }
        } while (gap > 1);
}

      好了让我们测试一下这个算法吧，main函数根据根据输入参数随机生成input数组，然后把input传给sort函数进行排序，然后输出结果，测试程序如下：

#include  <time.h></time.h>
#define   MAXSIZE   1000

int main(void)
{
      int input[MAXSIZE+1];
      int  n, i;
      char line[100];

      printf("\nSort Program Testing Driver for Random Data");
      printf("\n-------------------------------------------");
      printf("\n number of the item");
      gets(line);
      n = atoi(line);
      srand((unsigned)clock());
      printf("\nGenerated Data :");
      for(i = 0; i < n; i++)
      {
            if (i % 10 == 0)  printf("\n");
            input[i] = rand();
            printf("%6d", input[i]);
      }
      sort(input, n);
      printf("\n\nSorted Data :");
      for (i = 0; i < n; i++)
      {
            if (i % 10 == 0)  printf("\n");
            printf("%6d", input[i]);
      }
      getchar();
}