希 尔 排 序

基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。

序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：h_t=2^t-1,1≤t≤[log₂n]，其中n为待排序序列的长度。

    C函数如下：

  void prshl(p,n)

  int n;double p[];

  {

   int k,j,i;

   double t;

   k=n/2;

   while(k>0)

   {

    for(j=k;j<=n-1;j++)

    {

      t=p[j];i=j-k;

      while((i>=0)&&(p[i]>t))

        {

         p[i+k]=p[i];i=i-k;

         }

       p[i+k]=t;

      }

      k=k/2;

     }

   return;

  }