希尔排序(c++)

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。^[1]

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比^[2] 较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

希尔排序的执行时间依赖于增量序列，好的增量序列的共同特征为：
1 最后一个增量必须为1

2 应该尽量避免序列中的值（尤其是相邻的值）互为倍数的关系

1，5，7，4，55，90，10，45，75，3，20 共11个数增量为11/2

1 90 20

1 20 90

5 10

7 45

4 75

55 3

3 55

1，5，7，4，3，20，10，45，75，55，90 增量为5/2

1 7 3 10 75 90

1 3 7 10 75 90

5 4 20 45 55

4 5 20 45 55

1，4，3，5，7，20，10，45，75，55，90 增量为1

按照直接插入排序

1，3，4，5，7，10，20，45，55，75，90

void ShellSort(int*data,unsigned int len){
    if(len<=1||data==NULL)
    return;
    for(int div=len/2; div>=1; div/=2){
        for(int i=div; i<len; i++){
            for(int j=i; (data[j]<data[j-div])&&j>=0; j-=div){
                swapInt(data+j,data+j-div);
            }
        }
    }
}