七大排序之希尔排序

<ShellSort>
基本思想：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
希尔增量：gap=length/2，缩小增量继续以gap = gap/2的方式。此时时间复杂度为O(n^2)。
实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时，可以采用元素交换法寻找最终位置，也可以采用数组元素移动法寻觅。

void ShellSort(int *a,int lo,int hi)
{
    
    if(hi-lo<1) return;
    unsigned int len=hi-lo+1;
    int insertnum;
    unsigned int gap=len/2;
    while(gap)
    {
        for(unsigned int i = gap+lo;i<lo+len;++i)
        {
            insertnum=a[i];
            unsigned int j = i;
            while(j>=gap+lo && insertnum<a[j-gap])
            {
                a[j]=a[j-gap];
                j-=gap;
            }
            a[j] = insertnum;
        }
        gap/=2;
    }
}