1. 简介
在本文中，我们将讨论 Shellsort 的时间复杂度。Shellsort 是一种基于插入排序的改进算法，其性能与所使用的 gap sequence（间隔序列） 紧密相关。
2. Shellsort 原理
Shellsort 利用了一个数组的性质：一个排序后的数组的任意子序列也是排序后的。
举个例子，如果数组 x 是升序排列的，那么无论我们如何选取下标，这些下标的元素组成的子序列也必然是升序的。
Shellsort 的核心思想是：
- 将数组划分为多个“链”（chains），每条链由固定间隔（gap）的元素组成
- 对每条链进行插入排序
- 逐步减小间隔，重复排序，直到间隔为 1（即对整个数组进行一次插入排序）
这样做的好处是：大间隔排序能让元素“跳跃”到更接近正确的位置，从而减少后续小间隔排序的工作量。
2.1 示例图解
当数组长度为 16，gap = 4 时，会形成 5 条链：
2.2 伪代码
algorithm Shellsort(x, h):
// x: 待排序数组
// h: gap 序列，例如 [7, 3, 1]
for k <- 1 to m: // 遍历每个 gap
for i <- 1 to h[k] + 1:
r <- floor((n - i) / (h[k] + 1))
Apply Insertion Sort to chain [x[i + t * (h[k] + 1)] | t = 0, 1, ..., r]
return x
2.3 关键点总结
✅ 每次排序的是“间隔”为 h[k] 的子数组
✅ 最后一次 gap 为 1，确保最终数组有序
✅ 插入排序的高效性在“部分有序”数组中表现更佳
❌ gap 序列选择对性能影响巨大
3. 时间复杂度分析
Shellsort 的时间复杂度 完全取决于所使用的 gap sequence。目前没有统一的公式可以准确计算任意 gap 序列下的时间复杂度，因此必须 逐个分析。
3.1 Shell 原始序列
Shell 最初使用的 gap 序列为：
h_k = ⌈n/2⌉, ⌈n/4⌉, ..., 1
比如 n = 16，gap 序列为：8, 4, 2, 1
最坏情况分析
当 n 是 2 的幂，且奇数位和偶数位分别有序时，插入排序在最后一次 gap=1 时会进行大量交换。
最终交换次数为：
$$ \sum_{i=1}^{n/2 - 1} i = \frac{n^2}{8} \in \Theta(n^2) $$
✅ 结论：使用 Shell 原始 gap 序列，最坏时间复杂度为 O(n²)
3.2 Hibbard 序列
Hibbard 提出的 gap 序列为：
$$ h_k = 2^k - 1 $$
比如 n = 14，gap 序列为：7, 3, 1
✅ 结论：使用 Hibbard 序列，最坏时间复杂度为 O(n¹·⁵)
3.3 Pratt 序列
Pratt 提出的 gap 序列由如下形式的数构成：
$$ 2^p \cdot 3^q $$
比如：1, 2, 3, 4, 6, 8, 9, ...
✅ 结论：使用 Pratt 序列，最坏时间复杂度为 O(n (log n)²)
⚠️ 缺点：gap 数量多，实际运行速度慢
3.4 常见 gap 序列对比
| Gap Sequence | 时间复杂度 | 备注 |
|---|---|---|
| Shell 原始 | O(n²) | 简单但效率差 |
| Hibbard | O(n¹·⁵) | 性能提升明显 |
| Pratt | O(n (log n)²) | 当前最优理论复杂度 |
| Sedgewick | O(n⁴/³) | 实用性较强 |
| Tokuda | O(n log² n) | 现代实现常用 |
4. 空间复杂度
Shellsort 是原地排序算法，只使用常数级的额外空间。
✅ 空间复杂度：O(1)
5. 总结
Shellsort 的时间复杂度高度依赖于所使用的 gap 序列。目前尚无统一的最优 gap 序列，不同序列在理论和实际性能上表现差异显著。
| 关键点 | 说明 |
|---|---|
| ✅ 最优理论复杂度 | O(n (log n)²)（Pratt） |
| ❌ 最差复杂度 | O(n²)（Shell 原始） |
| ✅ 实用 gap 序列 | Hibbard、Sedgewick、Tokuda |
| ⚠️ 踩坑提示 | 不恰当的 gap 序列可能导致性能退化为 O(n²) |
| ✅ 空间效率 | 原地排序，O(1) 空间 |
✅ 总结：Shellsort 是一种简单但性能依赖于 gap 序列的排序算法。合理选择 gap 可以达到接近 O(n log n) 的性能，但设计最优 gap 仍是开放问题。