shell排序法

shell排序法又称为增量排序法，它属于插入排序法的一种。它的基本思想是，在多趟排序中，设置不同的增量，增量从大到小，最后的增量设置为1，如......5，3，1。最终完成排序。它的实质是将数据进行分组插入排序。

例如有下列一组数字进行shell排序：
81  94  11  96  12  35  17  95  28  58  41  75  15

设第一趟增量为 5，        81  94  11  96  12  35  17  95  28  58  41  75  15
第一趟排序后，              35  17  11  28  12  41  75  15  96  58  81  94  95

设第二趟增量为 3，        35  17  11  28  12  41  75  15  96  58  81  94  95
第二趟排序后，              28  12  11  35  15  41  58  17  94  75  81  96  95

设第三趟增量为 3，        28  12  11  35  15  41  58  17  94  75  81  96  95
第三趟排序后，              11  12  15  17  28  35  41  58  75  81  94  95  96

shell算法的运行时间与所设增量有密切的关系。一般情况下使用素数做为增量，如1，3，5，7，11......

算法：
void shellpass(int dt, int arr[], int N)
{
    int i,j;
    int tmp;
   
    for(i=dt; i<=N；i++)
    {
        tmp = arr[i];
        for(j = i; j>dt && arr[j] >tmp; j-=dt)
            arr[j] = arr[j-dt];
        arr[j] = tmp;
    }

  }

  void  shellsort(int arr[], int N)
  {
      do {
          increment=increment/3+1；     //求下一增量
          shellpass(increment, arr[], N)； //一趟增量为increment的Shell插入排序
       }while(increment>1)
  }