算法系列之五 希尔排序

  • 2018-05-12
  • 269
  • 0

对于前面讲过的基础排序来说,他们在实际使用的时候,价值并不是太大。它的价值在于,体现了一种很好的思想。通过一些改进和变化,可以达到一个不错的性能。希尔排序就是典型的一个例子,它改进了插入排序,使得算法的实用性大大增加,对于中等数组,当需要用排序解决问题,又不能使用系统排序的时候,这是一个不错的选择。

希尔排序的思想

首先,我们来回忆一下,插入排序的优点,它有两个优点:

  1. 对于小数列的速度很快(所以被用来做其他高级排序在小数列情况下的优化实现)
  2. 依赖输入,对于接近有序的数列很快

希尔排序就是充分利用了这两个优点,来优化插入排序。那么,希尔排序做了哪些改动呢:

1. 将数组分隔成更小的数组

希尔排序假设一个值 h, 将数列中,间隔为 h 的元素,作为一个新的子数列,这时,将整个大的数列分成了若干小数列,然后挨个处理子数列。因为 优点1,所以希尔排序会表现得很快。然后减小 h 的值,直到 1。

2. 对基本有序的大数列排序

h=1 的时候,就是对整个数组运行一遍插入排序,数组有序。因为之前的操作,使得整个数列已经处于基本有序的状态了。这时充分利用了 优点2,排序也会表现得很快。

代码如下:

void shell_sort(int *a, int length) {

    int h;
    // 选择一个 小于数组长度,可能最大的间隔值
    // 1, 4, 13, 40, 121, 364 ....
    for (h = 1; h < length / 3; h = 3 * h + 1);

    while (h >= 1) {

        // 对间隔 h 的每个元素进行处理
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && a[j-h] > a[j]; j -= h) {
                swap(a, j, j - h);
            }
        }
        h = h / 3;
    }
}

上面的代码中,在第一个for循环的地方,产生了一个递增的数列。后面的 while 循环,按照这个数列来递减,处理整个待排序数组。

希尔排序的性能,很大程度上取决于这个 递增数列。所以,如何产生这个数列是一个值得研究的话题。有很多论文研究了各种不同的递增数列,但是都没有办法证明是最好的。

对于一些复杂实现的 递增数列,在最坏的情况下,性能要好于我们这个版本的。但是,在平均的情况下,使用 3*h+1 这个简单的方法,和复杂实现的性能是接近的。

结尾

希尔排序的性能计算一直是一个很难的问题。目前只能说,它是小于插入排序的 \(O(N^2)\) 的复杂度。在我们的版本中,已知最坏的情况下,比较次数和 \(N^{3/2}\)成正比。

但是,通过一点小的改变就能,就能突破平方级,是很多算法设计要达到的目标。

作者和出处(reposkeeper) 授权分享 By CC BY-SA 4.0 Creative Commons License

关注微信公众号,获取新文章的推送!
qrcode

评论

还没有任何评论,你来说两句吧

发表评论

*

code