这两个排序算法关系度极高,可以理解为希尔排序=插入排序plus,即希尔排序是在插入排序的基础上修改的,所以我们先从插入排序开始,分析一下这两个算法。

一、插入排序

1、思想

插入排序是维持一系列已排序元素,然后逐渐扩大它(即把要元素插入到已排序的序列的对应位置中)直到让整个数组全部排序完成。
我描述得可能很奇怪(抱歉,过于渣渣了),但大家可以联想一下打牌的时候的一种整理情况:拿起的牌中可能有某几张已经有序了,此时我们以它为基础,把其它牌一张一张地插入到已经有序的牌的对应位置中(此时仍要保证它部分有序),直到所有牌都整理好。

具体实现的步骤是:对于每一个要排序的元素,检查与前一个元素的大小关系(即比较),然后将该元素前移,直到合适的位置为止。对每一个元素都进行如上的操作,即可把整个数组排序完毕。

2、具体实现

下面会展示两种实现的方法,核心是一样的,只是具体实现上有一点点细小的差别。

交换式

a.代码实现

这是红圣经《算法》第四版中的实现。
它采用的数据前移的方法,是交换
条件合适的话,一直与前一个元素进行交换。

for(int i = 1;i < nums.length;i++){
    // 若要交换的元素比前一个元素还小,则要向前移动(即与之交换)
    for(int j = i; j > 0 && nums[j] < nums[j - 1];j--){
        int t = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = t;
    }
}
b.结果

image.png


覆盖式

a.代码实现

很容易就发现,这种交换有极大的浪费,极端点的,前面交换了这么多次,就是为了最后那次移动,显然有点吃亏。
所以可以先保存要移动的元素,然后让符合条件的元素向后覆盖,然后把保存了的元素放到对应位置中。
这个做法可以减少元素的交换,使效率提高。

for(int i = 1;i < nums.length;i++){
    // 保存,以免被覆盖
    int t = nums[i];
    int j;
    for(j = i; j > 0 && t < nums[j - 1];j--){
        nums[j] = nums[j - 1];
    }
    // 再在对应位置赋值
    nums[j] = t;
}
b.结果

image.png

3、分析

可以发现插入排序的效率与数组初始状态有关,对于部分有序规模较小的数组,使用插入排序的效率还是十分高效的。
假如一个数组已经有序,那么它的运行时间是线性级别的(而选择排序则是平方级别)。

红圣经中还给出这么个结论:对于随机排列的长度为N且主键不重复的数组,平均情况下插入排序需要 ~ $N2/4$次比较及 ~ $N2/4$次交换。最坏情况下需要 ~ $N2/2$次比较及 ~ $N2/2$次交换,最好情况下需要$N-1$次比较及0次交换。

上面的数据是怎样来的呢?下面逐个来分析。

先看最好的情况,就是元素都有序,那么交换次数为0;从第二个元素开始,都是向前比较,总共比较的次数就是N-1了。

最坏的情况,则是数组逆序,那么就和我的选择排序中分析的一样。

每种情况出现的可能都是随机的,所以平均情况。。。就(最好+最坏)/2 ? (似乎有点不大严谨)。

遇到这种分析就感觉很数学,但还是得试着接受这些。

4、与选择排序相比较

在这两种初级排序算法中,到时谁更胜一筹呢?
其实有学过这个的都知道,这两种算法时间复杂度都在$O(N^2)$级别,不大行。
但是呢,我们有分析过他们的比较次数和交换次数,知道它们其实是有一点差距的,它们的运行时间是平方级别的,两者之比是一个较小的常数

模仿红圣经里面的做法

先计算t次随机排序所需时间

public static double timeRandomInput(String alg, int N, int T) {
        double total = 0.0;
        Double[] a = new Double[N];
        // 生成T个长度为N的随机数组,排序并计时
        for (int t = 0; t < T; t++) {
            for (int i = 0; i < N; i++) {
                a[i] = StdRandom.uniform();
            }
            // 累加每次排序所需时间
	    // time可以计算一次排序所需时间
            total += time(alg, a);
        }
        return total;
}

然后进行比较

public static void main(String[] args) {
    String alg1 = "Insertion";
    String alg2 = "Selection";
    // 数组长度为1000
    int N = 1000;
    // 比较10次
    int T = 10;
    // 计算所需时间
    double t1 = timeRandomInput(alg1, N, T);
    double t2 = timeRandomInput(alg2, N, T);
    StdOut.printf("For %d random Doubles \n    %s is", N, alg1);
    StdOut.printf(" %.1f times faster than %s\n", t2 / t1, alg2);
}

得到比较结果(每次都不同,但总体相差不大)

For 1000 random Doubles
Insertion is 1.4 times faster than Selection

经过动手实验可以知道,一般情况下,插入排序的效率是比选择排序高的,而且它们运行时间之比是一个小常数。

二、希尔排序

1、思想

其实上面说到,对于部分有序、规模小的的数据,使用插入排序的效率会很高,而希尔排序正是通过这个思想,来创造条件使得插入排序的效率变高。

下面来思考这么种情况,在升序的插入排序中,最小的元素在数组的尽头,那么就要移动$N-1$次才能把它放在正确的位置。有没有一种方法能减少移动的次数呢?
有,那就是就是希尔排序,为了加快插入排序的速度,它先对不相邻的元素进行局部排序,最后才进行插入排序。

希尔排序是想让任意间隔h的数组都是有序的。
h是一个以1结尾的序列,比如:1,4,13,40,121...($\frac{3^k-1}{2}$)可以任意设置,但要找一个高效的,可以参照书本给的例子。(这是一个数学问题,至今都没有找到“最好的”h序列)

这是什么意思呢?
下面是h=4时,任意数组对一轮希尔对间隔为4的元素进行排序。
image.png

可以看到,整个数组被划分成了若干个小数组,然后对各自小数组进行排序。
这样做有以下好处:

  1. 把原数组拆分成数个规模小的数组,适用于插入排序。
  2. 经过若干个次h间隔的排序,整个数组已经是接近有序的,为最后的插入排序提供更高效的条件。

2、实现

理解了插入排序之后,希尔排序很简单。
创建一个结尾为1的h序列,从大到小,都数组进行间隔为h的插入排序。
我们假定h序列符合$\frac{3^k-1}{2}$。

h序列是可以自己定的,下面代码是即时计算,也可以使用数组保存。

int h = 1;
// 创建h序列(也可以使用数组保存)
while(h < nums.length / 3){
    h = 3 * h + 1;
}
while(h >= 1){
    // 插入排序,不过是间隔h的
    // 感受一下它和普通的插入排序有什么不同
    for(int i = h;i < nums.length;i++){
        int t = nums[i];
        int j;
        // 注意修改条件,是间隔h的!
        // 还要小心越界
        for(j = i; j >= h && t < nums[j - h];j -= h){
            nums[j] = nums[j - h];
        }
        // 再在对应位置赋值
        nums[j] = t;
    }
    // 每次都除以3,缩小回上一个h
    h /= 3;
}

3、效率相关

目前,似乎科学家们并未能对希尔排序的性能给出一个确定的答案,但可以肯定的是,希尔排序突破了平方级别的运行时间,远比插入排序效率要高。将插入排序作一个小小的改变就有这样的效果,真的有趣。

image.png

对于希尔排序,它的代码量很少,无需额外空间,对于中等大小的数组,它的运行时间是可以接受的。若N特别大时,一些更高级的算法的运行时间也只是比希尔排序要快近两倍而已。

对于考试来说,可以记住的是:时间复杂度$O(nlogn)$,空间复杂度$O(1)$。