本文记述了希尔排序的基本思想和一份参考实现代码，并在说明了算法的性能后用随机数据进行了验证。
◆ 思想
给定元素之间的间隔 h ，将所有间隔为 h 的元素作为独立的待排序范围，可以得到 h 个这样的子范围。针对每个子范围执行插入排序，使得任意间隔为 h 的元素是有序的。然后缩小间距 h，对新的子范围重复以上的插入排序，直到间隔 h 递减至 1 为止（间距 h 的计算基于理论研究）。如要得到逆序的结果，则仅需改变比较的方向即可。
◆ 实现
排序代码采用《算法（第4版）》的“排序算法类模板”实现。(代码中涉及的基础类，如 Array，请参考算法文章中涉及的若干基础类的主要API）
// shell.hxx
...
class Shell
{
...
template
<
class _T,
class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
>
static
void
sort(Array<_T> & a)
{
int N = a.size();
int h = 1;
while (h < N/3) h = 3*h + 1; // #1
while (h >= 1) {
for (int i = h; i < N; ++i) { // #2
_T t = a[i];
int j;
for (j = i; j >= h && __less__(t, a[j-h]); j -= h)
a[j] = a[j-h];
a[j] = t;
}
h /= 3; // #1
}
}
...
template
<
class _T,
class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
>
static
bool
__less__(_T const& v, _T const& w)
{
return v.compare_to(w) < 0; // #3
}
...
使用简单的公式计算间距（#1）。针对每个子范围执行不需要交换的插入排序（#2）。将 '<' 改为 '>'，即得到逆序的结果（#3）。
◆ 性能
| 时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|
| N^(6/5) ? N^(5/4) ? | 1 | 否 |
【注】“透彻理解希尔排序的性能至今仍然是一项挑战。... 算法的性能不仅取决于 h，还取决于 h 之间的数学性质，...”（引《算法（第4版）》）。
◆ 验证
测试代码采用《算法（第4版）》的倍率实验方案，用随机数据验证其正确性并获取时间复杂度数据。
// test.cpp
...
time_trial(int N)
{
Array<Double> a(N);
for (int i = 0; i < N; ++i) a[i] = Std_Random::random(); // #1
Stopwatch timer;
Shell::sort(a); // #2
double time = timer.elapsed_time();
assert(Shell::is_sorted(a)); // #3
return time;
}
...
test(char * argv[])
{
int T = std::stoi(argv[1]); // #4
double prev = time_trial(512);
Std_Out::printf("%10s%10s%7s\n", "N", "Time", "Ratio");
for (int i = 0, N = 1024; i < T; ++i, N += N) { // #5
double time = time_trial(N);
Std_Out::printf("%10d%10.3f%7.1f\n", N, time, time/prev); // #6
prev = time;
}
}
...
用 [0,1) 之间的实数初始化待排序数组（#1），打开计时器后执行排序（#2），确保得到正确的排序结果（#3）。整个测试过程要执行 T 次排序（#4）。每次执行排序的数据规模都会翻倍（#5），并以上一次排序的时间为基础计算倍率（#6），
此测试在实验环境一中完成，
$ g++ -std=c++11 test.cpp std_out.cpp std_random.cpp stopwatch.cpp type_wrappers.cpp
$ ./a.out 8
N Time Ratio
1024 0.006 3.0
2048 0.015 2.5
4096 0.037 2.5
8192 0.086 2.3
16384 0.197 2.3
32768 0.462 2.3
65536 1.091 2.4
131072 2.549 2.3
可以看出，随着数据规模的成倍增长，排序所花费的时间将是上一次规模的 2.3 倍。将数据反映到以 2 为底数的对数坐标系中，可以得到如下图像，
O(N^(6/5)) 代表了（6/5）次方级别复杂度下的理论排序时间，该行中的数据是以 Time 行的第一个数据为基数逐一乘 2^(6/5) 后得到的结果（因为做的是倍率实验，所以乘 (2)^(6/5) 即 2.29）。
O(N^(5/4)) 代表了（5/4）次方级别复杂度下的理论排序时间，该行中的数据是以 Time 行的第一个数据为基数逐一乘 2^(5/4) 后得到的结果（因为做的是倍率实验，所以乘 (2)^(5/4) 即 2.37）。
◆ 最后
完整的代码请参考 [gitee] cnblogs/18137029 。
写作过程中，笔者参考了《算法（第4版）》的希尔排序、“排序算法类模板”和倍率实验。致作者 Sedgwick，Wayne 及译者谢路云。
标签：...,int,算法,希尔,time,cpp,排序 From： https://www.cnblogs.com/green-cnblogs/p/18137029