希尔排序

希尔排序（Shell Sort）是希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序是一种插入排序，它是将简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，该算法是冲破 \(O(n^2)\) 时间复杂度的第一批算法之一。

希尔排序是把序列按下标的一定增量分组，对每组使用插入排序算法排序；这样多轮次执行，随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个序列恰被分成一组并使用插入排序算法排序，这样整个序列有序，算法也终止。

简单插入排序循规蹈矩，不管数组分布是怎么样的，就是逐步对元素进行比较、移动、插入，例如 [5,4,3,2,1,0] 这种倒序序列，数组末端的 0 要回到首位置很是费劲，比较和移动元素均需 \(n-1\) 次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为 1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为 1 时，其实多数情况下只需微调即可，不会涉及过多的数据移动。可见希尔排序的效率要高于插入排序。

来看下希尔排序的基本步骤，在此选择增量 \(gap=n/2\)，缩小增量只需要反复执行 \(gap = gap/2\) 直到 \(gap==0\) 为止，这种增量选择可以用一个序列来表示——\(\{n/2,(n/2)/2,…,1\}\)——称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，这里选择的这个增量序列是比较常用的，也是算法提出者希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

下面给出希尔排序的参考代码，注意体会跳跃性前插的实现：

//希尔排序：对数组的r[0]~r[n-1]区域排序（升序排序） 
void ShellSort(int r[],int n){
    for(int gap=n/2;gap;gap/=2){
    	//r[0]、r[gap]、r[gap*2]...是一组
    	//r[1]、r[gap+1]、r[gap*2+1]...是一组
    	//r[2]、r[gap+2]、r[gap*2+2]...是一组
    	//...
		//r[gap-1]、r[gap*2-1]、r[gap*3-1]...是一组
		//每组第2个元素开始，考察前插（跳跃性前插） 
        for(int i=gap;i<n;i++){
            //r[i],r[i-gap],r[i-gap-gap]...是一组的已有序区域，将r[i]前插到组内合适位置 
            int x = r[i],k = i-gap;  //前插后移会覆盖掉r[i]，所以先将r[i]保存到x中
            while(k>=0 && x<r[k]){   //x<r[k]，那么x插入的位置还能再靠前
                r[k+gap] = r[k];
                k -= gap;
            } 
            r[k+gap] = x;
        }
    }
}
//调用方法举例：ShellSort(a,10);
//调用方法举例：ShellSort(a,n);

仿照 sort 函数的写法，用两个指针作为函数参数来指定排序的区域：

//希尔排序：对指针begin~end区域排序（升序排序，不包括end）
void ShellSort(int *begin,int *end){
	int n = end-begin; 
    for(int gap=n/2;gap;gap/=2){
    	//*begin、*(begin+gap)、*(begin+gap*2)...是一组
    	//*(begin+1)、*(begin+gap+1)、*(begin+gap*2+1)...是一组
    	//*(begin+2)、*(begin+gap+2)、*(begin+gap*2+2)...是一组
    	//...
		//*(begin+gap-1)、*(begin+2*gap-1)、*(begin+gap*3-1)...是一组
		//每组第2个元素开始，考察前插（跳跃性前插）  
        for(int *p=begin+gap;p<end;p++){
            //*p,*(p-gap),*(p-gap-gap)...是一组的已有序区域，将*p前插到组内合适位置 
            int x = *p,*q = p-gap;  //前插后移会覆盖掉*p，所以先将*p保存到x中
            while(q>=begin && x < *q){   //x < *q，那么x插入的位置还能再靠前
                *(q+gap) = *q;
                q -= gap;
            } 
            *(q+gap) = x;
        }
    }
}
//调用方法举例：ShellSort(a,a+10);
//调用方法举例：ShellSort(a,a+n);
//调用方法举例：ShellSort(a+1,a+n+1);

希尔排序中增量序列的选择十分重要，直接影响到希尔排序的性能。上面选择的增量序列 \(\{n/2,(n/2)/2,…,1\}\)（希尔增量），其最坏时间复杂度依然为 \(O(n^2)\)，平均时间复杂度为 \(O(nlogn)\)，一些经过优化的增量序列，如Hibbard经过复杂证明可使得最坏时间复杂度为 \(O(n^{3/2})\)。希尔排序是插入排序的改良版，插入排序是稳定排序，但是希尔排序插入的过程中会出现跳跃性插入的情况，导致希尔排序不稳定。