希尔排序¶

前置知识¶

插入排序，分组思想

目标¶

算法思路，代码模板

希尔排序¶

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率

但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

算法思想：

把序列按下标的一定增量分组（增量初始值可为 len / 2），对每组使用直接插入排序算法排序

随着增量逐渐减少，每组包含的关键词越来越多

当增量减至1时，整个序列恰被分成一组，算法便终止

平均时间复杂度，根据步长序列的不同而不同。

最坏时间复杂度，根据步长序列的不同而不同。已知最好的是 \(O(nlog^2n)\)

最优时间复杂度，\(O(1)\)

空间复杂度，\(O(1)\)

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]。

如果我们以步长为 5 开始进行排序，我们可以通过将这列表放在有 5 列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。

这时 10 已经移至正确位置了，然后再以 3 为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）。

步长¶

步长的选择是希尔排序的重要部分。只要最终步长为 1 任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为普通插入排序，这就保证了数据一定会被排序。

“比较在希尔排序中是最主要的操作，而不是交换。”

用合适的步长，希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

代码模板¶

#include <bits/stdc++.h>

using namespace std;

int a[110], n;

void shell_sort(int a[], int len) {
    int step = 1;
    while (step < len / 3) step = 3 * step + 1;

    while (step >= 1) {
        for (int i = step; i < len; i++)
            for (int j = i; j >= step && a[j] < a[j - step]; j -= step)
                swap(a[j], a[j - step]);

        step /= 3;
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    shell_sort(a, n);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");

    return 0;
}

参考¶

https://en.wikipedia.org/wiki/Shellsort

https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

图解排序算法(二)之希尔排序