Shellsort

最近复习了《数据结构与算法分析》这本书，看到希尔排序的时候感触很深。故欲与大家分享学习。

wiki的图解如下

引言
了解希尔排序首先需要了解插入排序。插入排序就与我们自然的排序很像。例如:

初始	34 8 64 51 32 31	移动的位置
在p=1之后	8 34 64 51 32 31	1
在p=2之后	8 34 64 51 32 31	0
在p=3之后	8 34 51 64 32 31	1
在p=4之后	8 32 34 51 64 31	3
在p=5之后	8 31 32 34 51 64	4

插入排序分析

观察发现其实每次对已经排序的队列也要一一对比。比如在 4 位置的32 需要比较 64 51 34 8 。但是 64 51 34 本身已经排序过了。

嵌套循环每一个都必须花费N次迭代，因此插入排序复杂度为O( $N^2$ )。

希尔排序

名字源于发明者，具体可以在参考链接中查看。这里直接主题了。

排序本质就是消除逆序数。希尔排序、快速排序等突破二次时间屏障的排序原理相同，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序数。

希尔排序使用一个序列 $h_1,h_2 ,...h_t$ ,叫做增量序列。只要 $h_1 = 1$ ，其它任何增量都是可行的，取值不同最后的效率也会有所不同。希尔排序重要的性质是一个 $h_{k^-}$ 排序的文件保持它的 $h_{k^-}$ 排序性。因为前面各趟排序的结果会被后面各趟排序给打乱。一般增量序列会选择 $h_t = N/2$ 和 $h_{k+1}/2$ 。增量序列有时候可能会对算法性能造成剧烈的影响。

到这里你如果还没有看懂增量序列什么意思，下图的例子可能会明确一些。假设增量序列为［1，3，5］，排序数组为 [13,81,94,23,45,8,22,41,88,92,99,31,21]

那么首先我们以 5 为步进 (5组的意思)

组1	组2	组3	组4	组5
13	81	94	23	45
8	22	41	88	92
99	31	21

对其进行排序

组1	组2	组3	组4	组5
8	22	21	23	45
13	31	41	88	92
99	81	94

然后结果为 [8,22,21,23,45,13,31,41,88,92,99,81,94] 同理进行以3为步进（3组），最后以1为步进（1组）。

可以看这个blog，他里面的图表示也十分明确。其实并不是真正的分组，就是就是加快逆序数的位置交换。

贴上C语言的源代码。

//
// Created by fan on 16/10/9.
//
#include "stdio.h"

void
Shellsort(int  *A,int N){
    int i , j ,Increment;
    int Tmp;
    int pp = *(A+1);
    int p2 = A[1];
    for (Increment = N /2 ; Increment > 0; Increment /=2 ) {
        for (i = Increment; i < N; i++) {
            Tmp = A[i];
            for (j = i; j >= Increment; j -= Increment) {
                if (Tmp < A[j - Increment])
                    A[j] = A[j - Increment];
                else
                    break;

            }
            A[j] = Tmp;
        }
    }
}
int main(int argc, char *argv[]){
    int  list[5] ={2,13,44,15,3};
     Shellsort(&list,5);

    int i = 0;
    for (i = 0; i < 5; ++i) {
        int a = list[i];
        printf("%d \n",a);
    }
}

希尔排序最坏情况分析

希尔排序运行时间或者说效率十分依赖增量序列的选择。什么时候排序效果最差，举个例子，如果我们选择了一个N是2的幂。这样除了最后一个增量是1之外都是偶数（例如增量 8 4 2 1 ）。且我们的数组为偶数位 N/2 是最大的数，奇数位为最小的数（例如 [1,9,2,10,3,11,4,12]）。那么前几次排序后，输入队列一直保持不变。

希尔增量的问题在于，增量对未必互素，因此给出较小的增量可能影响很小。

具体希尔排序的最坏情况证明涉及到许多的数学运算，这里就不展开说明。有兴趣可以点击下面的参考链接以及Google希尔排序的最坏情况。

References:

https://en.wikipedia.org/wiki/Shellsort
https://zh.wikipedia.org/wiki/希尔排序