希尔排序

希尔排序

不断缩小增量的插入排序

原理

以某个增量h为步长跳跃分组进行插入排序，增量是一个从h逐渐缩小至1的过程，所以又称缩小增量排序。 

其核心在于间隔序列设定，是与插入排序的本质区别。插入排序始终增量为1。 

最佳增量: k趟排序增量步长为(2^k)-1,即增量序列(2^k)-1,…15,7,3,1

分析

时间复杂度：nlogn

代码

void shellsort(int a[],int len){
    int gap = len;
    while(gap = gap/2){//增量
        for(int i=gap;i<len;i++){//下面的就是插入排序，间距为gap
            int key=a[i];
            int j=i-gap;
            while(j>=0 && a[j]>key){
                a[j+gap] = a[j];
                j-=gap;
            }
            a[j+gap] = key;
        }
    }
}