希尔排序（Shell Sort）
希尔排序的本质，是先用大步长把明显错位的元素提前搬近，再让最后一轮插入排序轻装上阵。
定义
希尔排序是插入排序的改进版本，也称为缩小增量排序。它通过比较相距一定间隔的元素来工作，逐步缩小间隔，最后间隔为1时就是普通插入排序。
核心思路
- 选择一个增量序列 t₁, t₂, …, tₖ，其中 tᵢ > tⱼ (i < j)，tₖ = 1
- 按增量序列个数k，对序列进行k轮排序
- 每轮采用插入排序，间隔为当前增量
- 增量逐渐减小，最后一轮增量为1
原数组: [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
gap=5: 将数组分为5组
[8, 3] [9, 5] [1, 4] [7, 6] [2, 0]
排序后: [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
gap=2: 将数组分为2组
[3, 1, 0, 9, 7] [5, 6, 8, 4, 2]
排序后: [0, 2, 1, 4, 3, 5, 6, 7, 8, 9]
gap=1: 普通插入排序
最终: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
为什么它比插入排序快
普通插入排序一次只能把元素往前挪一小步。
希尔排序先用较大的 gap 做“粗调”，快速减少逆序对，再用较小的 gap 做“细调”，最后 gap = 1 时，数组通常已经接近有序了。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n log n) | 取决于增量序列 |
| 平均时间 | O(n^1.3) | 经验值，取决于增量序列 |
| 最坏时间 | O(n²) | 最差情况 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | ❌ 不稳定 | 跨距离的交换破坏稳定性 |
注意：希尔排序的复杂度高度依赖于增量序列的选择。
Go 代码
Go 实现
package main
import "fmt"
func shellSort(arr []int) {
n := len(arr)
// 初始增量为n/2，逐步减半
for gap := n / 2; gap > 0; gap /= 2 {
// 对每个增量进行插入排序
for i := gap; i < n; i++ {
temp := arr[i]
j := i
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = temp
}
}
}
func main() {
arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
fmt.Println("原始数组:", arr)
shellSort(arr)
fmt.Println("排序后:", arr)
}易错点
希尔排序最容易被写成“只是把插入排序套了个壳”，但关键其实在增量设计。
gap序列不同，性能差异会很大。- 每一轮不是简单分组后单独排序，而是做“按 gap 取样的插入排序”。
- 它不稳定，因为远距离移动会打乱相等元素次序。
- 希尔排序适合中等规模数据，但不是面试里最核心的排序模板。
增量序列详解
经典题目
基础应用
- 排序数组 - LeetCode 912
- 实现不同增量序列的希尔排序
增量序列研究
- 比较不同增量序列的性能
- 找到最优增量序列
- 证明希尔排序的时间复杂度
优缺点
优点
- ✅ 比插入排序快很多
- ✅ 原地排序 O(1) 空间
- ✅ 实现简单
- ✅ 对中等规模数据效率高
- ✅ 自适应：对部分有序数据性能好
缺点
- ❌ 不稳定
- ❌ 复杂度分析困难
- ❌ 性能依赖增量序列
- ❌ 不如 O(n log n) 的算法
应用场景
- 中等规模数据：数据量在几千到几万
- 部分有序数据：数据基本有序
- 嵌入式系统：内存受限但需要比插入排序快
- 教学：展示算法改进思想
希尔排序的改进思想
希尔排序展示了如何改进简单算法：
- 插入排序的问题：每次只能移动一位，效率低
- 希尔的改进：先做”粗调”（大间隔），再做”细调”（小间隔）
- 预排序思想：通过预处理使数据”更有序”，加速最终排序
希尔排序 vs 插入排序
| 特性 | 希尔排序 | 插入排序 |
|---|---|---|
| 时间复杂度 | O(n^1.3) ~ O(n²) | O(n²) |
| 最好情况 | O(n log n) | O(n) |
| 稳定性 | 不稳定 | 稳定 |
| 实现难度 | 中等 | 简单 |
| 适用场景 | 中等数据 | 小数据/几乎有序 |
为什么希尔排序有效
- 减少逆序对：大间隔交换能快速减少逆序对数量
- 利用插入排序特性：插入排序对几乎有序的数据很快
- 预处理思想：先粗后细，逐步优化