C语言希尔排序及其增量序列

前情提要：C语言排序算法

插入排序的神奇之处在于，只要运气够好，甚至可以达到 O ( n ) O(n) O(n)的时间复杂度，希尔排序的思想就是想办法放大这种运气。

希尔排序又称缩小增量排序，据说是第一个突破 O ( n 2 ) O(n^2) O(n2)的排序算法，选择不同的增量，拥有不同的时间复杂度。

算法步骤 textbf{算法步骤} 算法步骤

设数组有 n n n个元素， { a 0 , a 1 , … , a n } {a_0,a_1,ldots,a_n} {a0​,a1​,…,an​}

1. 如果数组元素大于2，则将数组分成左数组和右数组，并对左数组和右数组的元素进行一对一地排序。
2. 对每一个数组进行细分，然后将每个子数组进行一对一地排序。

例如下面的数组

1 8 2 9 3 0 11 13 12 5 7 15 14 4 6 3

首先分为左右两个数组，对这两个数组按位排序

然后将左右两个数组再次分为左右两个数组，

那么现在总共有4列，左左、左右、右左、右右四列，为了书写方便，将左记为0，右记为1，这四列再分为8列

这时的序列为

1 0 2 3 3 4 6 5 7 8 11 9 12 13 14 15

还需要最后一步，即对这个序列进行排序。

问题的关键就是每次的组间排序用什么算法，如果用选择排序，那么希尔排序非但毫无意义，甚至会增加更多的时间。

如果使用插入排序，那么这两种算法在时间上的下限都是 O ( n ) O(n) O(n)，对于具有16个元素的数组而言，共需排序4次，每次需要

对于第2次排序，假设每一组的4位数字是abcd，所谓部分有序，就是存在

a < c , b < d a

而最差的情况无非是

b < d < a < c b

采用插入排序，其排序过程为abcd→bacd→bdac，其中，b和a需要比较一次，c和a比较一次，d和b,a,c分别比较一次，共需5次比较。

对于第三次排序，假设每一组的8位数字是abcdefgh，且存在

a < c < e < g , b < d < f < h a

则其最差的结果无非是

b < d < f < h < a < c < e < g b

要求abcdefgh→bdfhaceg，其变化过程为

1. abcdefgh
2. bacdefgh（b和a比较一次）
3. bdacefgh（c和a比较一次，d和b,a,c分别比较一次）
4. bdfacegh（e和c比较一次，f和d,a,c,e分别比较一次）
5. bdfhaceg（g和e比较一次，h和f,h,a,c,e分别比较一次）

共计16次比较。

对于长度为 2 N 2N 2N的序列 { a i } = a 1 a 2 . . . a 2 N {a_i}=a_1a_2...a_{2N} {ai​}=a1​a2​...a2N​，若其经过一次增量排序，则必符合

a i < a i + 2 a_iai​

其最差情况为

a 2 < a 4 < . . . < a 2 N < a 1 < a 3 < . . . < a 2 N − 1 a_2a2​

则由 a 1 a 2 . . . a 2 N a_1a_2...a_{2N} a1​a2​...a2N​变化为 a 2 a 4 . . . a 2 N a 1 . . . a 2 N − 1 a_2a_4...a_{2N}a_1...a_{2N-1} a2​a4​...a2N​a1​...a2N−1​的过程相当于是 a 2 a 4 . . . a 2 N a_2a_4...a_{2N} a2​a4​...a2N​逐一插入到 a 1 . . . a 2 N − 1 a_1...a_{2N-1} a1​...a2N−1​中，当 j > 1 j>1 j>1时， a 2 j a_{2j} a2j​的前面共有 j j j个 a 2 j − 1 a_{2j-1} a2j−1​，再算上已经排序完成的 a 2 j − 2 a_{2j-2} a2j−2​，则需要比较 j + 1 j+1 j+1次；而 a 2 j − 1 a_{2j-1} a2j−1​则只需和 a 2 j − 3 a_{2j-3} a2j−3​比较一次。

所以对于长度为 2 N 2N 2N的序列，共需比较

N + ∑ j = 2 j = N j + 1 = N + ( N − 1 ) ( N + 4 ) 2 N+sum_{j=2}^{j=N}j+1=N+frac{(N-1)(N+4)}{2} N+j=2∑j=N​j+1=N+2(N−1)(N+4)​

则对于长度为 2 N 2^N 2N的序列，希尔排序共需比较

∑ i = 1 N ( 2 i + ( 2 i − 1 ) ( 2 i + 4 ) 2 ) × 2 N − i = 2 N ∑ i = 1 N ( 1 + ( 1 − 2 − i ) ( 2 i + 4 ) 2 ) = 2 N ∑ i = 1 N ( 5 2 + 2 i − 1 + 2 1 − i ) ≈ 2 N ( 2 N − 1 ) begin{aligned} &sum_{i=1}^N(2^i+frac{(2^i-1)(2^i+4)}{2})times2^{N-i}\ =&2^Nsum_{i=1}^N(1+frac{(1-2^{-i})(2^i+4)}{2})\ =&2^Nsum_{i=1}^N(frac{5}{2}+2^{i-1}+2^{1-i})\ approx&2^N(2^N-1) end{aligned} ==≈​i=1∑N​(2i+2(2i−1)(2i+4)​)×2N−i2Ni=1∑N​(1+2(1−2−i)(2i+4)​)2Ni=1∑N​(25​+2i−1+21−i)2N(2N−1)​

可见，希尔排序在最差的情况下也需要 O ( n 2 ) O(n^2) O(n2)的时间复杂度，排序算法可用C语言写成下面的样子：

//希尔排序
void ShellSort(double *arr, int n){
    int i,j,nSub;
    for (nSub = n/2; nSub >0; nSub/=2)   //nSub为子数组长度
        for (i = nSub; i < n; i++)
        {
            tmp = arr[i];
            for (j = i-nSub; j >= 0 && tmp>arr[j]; j -= nSub)
                arr[j+nSub] = arr[j];
            arr[j+nSub] = tmp;
        }
}
int main(){
    testSort(6,InsertionSort,'>');
    return 0;
}

结果为

>gcc sort.c
>a
the original list: 927.50 1565.60 750.80 2276.00 1512.30 673.60
the sorted list: 2276.00>1565.60>1512.30>927.50>750.80>673.60

然而前面也提到了，希尔排序是第一个突破 O ( n 2 ) O(n^2) O(n2)的算法，怎么在这里失灵了呢？

主要是增量序列选的不对，刚刚选取的增量序列其实是

1 , 2 , 4 , . . . , 2 n 1,2,4,...,2^n 1,2,4,...,2n

很不幸是表现最差的增量序列之一，前人总结了一些高效的增量序列，

下面对Hibbard进行C语言实现，其中，步长为step的插入排序其实很简单，可直接修改插入排序

void ShellInsert(double *arr, int n, int s, int step){
    int j;
    for (int i = 1; i < (n-s)/step; i++){
        j = i;
        tmp  = arr[s+(j--)*step];
        while (tmp>arr[s+j*step] && j>0)
            arr[s+j*step] = arr[s+(--j)*step];  //第j个元素后移
        arr[s+j*step] = tmp;
    }
}

当然这种写法过于暴力，故稍作改动，然后进行排序

void shellInsert(double* arr, int n, int s, int step)
{
    int j;
    for (int i = s + step; i < n; i += step)
    {
        tmp = arr[i];
        j = i-step;
        while(tmp>arr[j] && j>s){
            arr[j] = arr[j-step];
            j -= step;
        }
        arr[j] = tmp;
    }
}

void HibbardSort(double* arr, int n)
{
    for(int step = (n+1)/2-1, step > 0 , step = (step+1)/2-1)
        for (int i = 0; i < step; i++)
            ShellInsert(arr, n, i, step);
}