Chapter2: 时间复杂度分析、递归、查找与排序

4. 希尔排序

1. 什么是希尔排序

概念解释

希尔排序也是一种插入排序，他是简单插入排序经过改进之后的一个更高效的版本，也称缩小增量排序。

希尔排序实质上就是对待排序序列进行分组，间隔一定距离进行局部的插入排序，不断缩小元素的间隔距离、减少分组，最终进行全部元素的插入排序。因为之前进行了局部的插入排序，所以在最后对全部元素进行插入排序时，元素已经基本有序了，整体而言希尔排序也比一般的插入排序更高效。

将一个序列分成好几个序列，那么到底怎么分呢？比如有10个元素的序列，分成几个才合适？每次缩减又是多少呢？

从专业的角度上讲，这个分组的数称为增量。显然的是，增量是不断递减的(直到增量为1)，一般而言，各趟排序的增量为{n/2,(n/2)/2...1}，每次增量都/2。

比如如果一个数列有10个元素，我们第一趟的增量是5(分为5组)，第二趟的增量是2，第三趟的增量是1。

希尔排序过程示意图

希尔排序示意图

2. 代码实现

/*希尔排序
参数:arr输入数组地址，arrLens数组长度 
*/

void shellSort(int* arr,int arrLen){
    for(int incre=arrLen/2;incre>0;incre/=2){
        for(int i=incre;i<arrLen;i+=incre){
            int tmp=arr[i];
            int j=i-incre;
            while(j>0 && tmp<arr[j]){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=tmp;
        }
        
    }
}