希尔排序的思路与C++实现

tags: DSA C++ Sort

写在前面

写一下希尔排序, 其实就是插入排序的升级版, 不是一次移动一个, 而是一次移动一组.

回顾插入排序

void InsertionSort(vector<int> &arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int tmp = arr[i], j = i;
        for (; j >= 0 && arr[j - 1] > tmp; --j) arr[j] = arr[j - 1];
        arr[j] = tmp;
    }
}

原理

这里参考了维基百科的原理分析,

​​希尔排序 - 维基百科，自由的百科全书 (wikipedia.org)​​;

例如，假设有这样一组数[ 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为步长进行排序：

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

排序之后变为：

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

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

代码

// 希尔排序, 递减增量排序算法
void ShellSort(vector<int>& arr) {
    int n = arr.size(), group = 3;
    // group:组数(行数), inc:间隔(列数)
    // 当间隔减小到1时, 完成排序
    for (int inc = n / group; inc > 0; inc /= group)
        // 对列做插入排序
        for (int i = inc; i < n; ++i) {
            int tmp = arr[i], j = i;
            for (; j >= inc && arr[j - inc] > tmp; j -= inc)
                arr[j] = arr[j - inc];
            arr[j] = tmp;
        }
}

从代码中可以看到, 希尔排序只是给插入排序套了一个外壳, 不同点在于新增加了步长和组数两个参数, 这就导致了其速度要快于插入排序.