希尔排序_希尔排序首趟间隔为4

希尔排序又叫间隔排序是插入排序的一种，但是在待排的数量多的时候希尔排序比直接插入排序的效率要高。

为什么这么说呢？因为直接插入排序是通过相邻两个比较，小的放前大的放后。如果一组数据中最小的数在最右边的话，那么在排这个最小数的时候所有数都得向有移动一位。而希尔排序不是一步步移动的，而是一大步一大步的移动的。即一开是给所有数据设定一个间隔将数据分组比较，再逐渐减小间隔分组比较，直到间隔为0时就排好序了。

为什么间隔分组比较就快速呢？当间隔大时，每组的个数就少，当间隔小时每组的个数多，但是也更接

近了最终排序了。

下面举例说明：

第一趟希尔排序，间隔为4

第二趟排序：间隔是2 

 

第三趟 间隔为1，即 直接插入排序法：

。。。。。

。。。。。

。。。。。

如何选择间隔？

 在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。因此，对于N=100的数组逐渐减小的间隔序列为50,25,12,6,3,1。这个方法的好处是不需要在不开始排序前为找到初始的间隔而计算序列；而只需要用2整除N。但是，这被证明并不是最好的数列。通过大量的实验证明间隔的选择可表达为下面的公式：h = h / 3 + 1;例如有1000个数的话，334，112，38，13，5，2，1

代码：

typedef int myDataType;
myDataType src_ary[10] = {9,1,5,8,3,7,6,0,2,4};

void shellSort(myDataType *ary,int len){
int i,j;
int increment = len;//增量
myDataType key;
while(increment > 1){//最后在增量为1并且是执行了情况下停止。
  increment = increment/3 + 1;//根据公式
  for (i=increment;i<len;i++){//从[0]开始，对相距增量步长的元素集合进行修改。
    key = ary[i];
    //以下和直接插入排序类似。
    j=i-increment;
    while(j >= 0){
      if (key < ary[j] ){
        myDataType temp = ary[j];
        ary[j] = key;
        ary[j+increment] = temp;
      }
      j=j-increment;
    }
  }
}
}


int _tmain(int argc, _TCHAR* argv[]){
  shellSort(src_ary,10);
  return 0;
}