写在前面
写一下希尔排序, 其实就是插入排序的升级版, 不是一次移动一个, 而是一次移动一组.
回顾插入排序
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;
}
}
原理
这里参考了维基百科的原理分析,
例如，假设有这样一组数[ 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;
}
}
从代码中可以看到, 希尔排序只是给插入排序套了一个外壳, 不同点在于新增加了步长和组数两个参数, 这就导致了其速度要快于插入排序.