希 尔 排 序

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

序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中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;

  }

希尔排序
它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

在希尔排序中，子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。如在第一趟排序时的增量为7，即将相隔为7的元素编成一组进行直接插入排序。第二趟排序时的增量为3，增量进一步缩小。由于在这两趟的插入排序中在子序列中逆序的关键字是跳跃式地移动，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。
下面用算法语言描述的希尔排序:

希尔排序中增量序列的选取是一个复杂的问题，涉及到一些数学上尚未解决的难题。我们不想加以详细讨论。到目前仅得出部分结论：如当增量序列为d[k]=2t-k+l -1时，希尔排序的运行时间为O(n3/2)，其中1≤k≤t≤└log2(n＋1)┘。增量序列还可以有各种取法, 如d[k]=2t-k，（d=…,9,5,3,2,1）。但请注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。

希尔排序:（搜索速度最好是O(logn),最坏是O(n^2)）
    例：初始状态：    49　38　65　97　76　13　27　*49  55  04
                      |                    |
                          |                    |
                               |                    |
                                  |                     |
                                       |                    |
    一趟排序的结果：13　27    *49　55    04　49　38　65　97　76
    　              ｜　　　　　 ｜　　　　 ｜　　　　　｜
                         |         |           |
                               |            |           |
    二趟排序的结果：13  04  *49  38  27  49  55  65  97  76
            
    三趟排序的结果：04　13　27　38　*49　49　55　65　76　97

增量公式：...9，5，3，2，1
    　...40，13，4，1

最后说下同一行都有带符号“|”的表示排序时将这几个比较后按大小排放