排序算法之希尔排序

1. 基本思想：分组式的插入排序。我的博客：排序算法之插入排序 中有详细介绍插入排序基本思想及其代码实现。

若数组大小为size，取一个小于size平分数组的整数n1作为第一个增量，把数组的所有元素分组，所有距离为n1倍数的元素相当于标记为一组，在各组内进行插入操作；再取一个小于n1的整数n2作为第二个增量，把数组的所有元素分组，所有距离为n2倍数的元素相当于标记为一组，在各组内进行插入排序；...直到取整数为1作为增量，相当于整个要排序的数被分为一组，此时直接进行插入排序。

此思想，是通过比较相隔较远（相隔的大小为增量）的元素使得元素移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。此算法先将要排序的数组按照某个步长（增量）分为若干组，每组中进行插入排序，然后再取较小的步长（增量）对数组进行分组并对各组进行插入排序，...当步长（增量）减到1时，整个数组元素被分为一组，对整个数组进行最后的插入排序。

一般对于增量的选择，使用的是希尔序列，即size/2、size/4、size/6、... 、1

2. 举例说明：待排序数组array[10]={70,30,40,10,80,20,90,100,75,60}

3. 代码实现如下（思路在代码中有详细解释）：

//思路:分组式进行插入排序
void ShellSort(int array[],int64_t size)
{
    //当size<=1时，不需要排序直接插入
    if(size<=1)
        return;
    //先定义一个希尔步长
    int64_t gap=size/2;
    //第一重循环用于生成步长序列
    for(;gap>0;gap/=2)
    {
        //定义边界bound
        int64_t bound=gap;//相当于插入排序bound=1
        //第二重循环，进行插入排序
        for(;bound<size;bound++)
        {
            //第三重循环，每组直接进行搬运
            int64_t cur=bound;
            int bound_value=array[bound];
            for(;cur>=gap;cur-=gap) //相当于插入排序中for(;cur>0;cur--)
            {
                if(array[cur-gap]>bound_value)//相当于插入排序中for(array[cur-1]<bound_value)
                {
                    array[cur]=array[cur-gap]; //相当于插入排序中array[cur]=array[cur-1]
                }
                else                                                                                                       
                {
                    break;
                }
            }
            array[cur]=bound_value;
        }
    }
}