希尔排序（Shell Sort）
基于插入排序的改进算法，通过预处理（使数组变成 h 有序）增加局部有序性，突破插入排序的 O(N²) 时间复杂度。
定义
希尔排序（Shell Sort）是插入排序的改进版本，由 Donald Shell 于 1959 年提出。其核心思想是：
- 先使数组变成 h 有序数组（对于任意间隔 h，间隔为 h 的元素都有序）
- 逐步减小 h 的值
- 当 h=1 时，数组已经基本有序，此时进行最后一次插入排序
核心特性
| 特性 | 说明 |
|---|---|
| 时间复杂度 | 取决于间隔序列，最优可达 O(n^1.3) 左右 |
| 空间复杂度 | O(1)，原地排序 |
| 稳定性 | ❌ 不稳定（间隔交换可能改变相同元素相对位置） |
| 是否原地 | ✅ 是 |
| 基础算法 | 插入排序 |
基本原理
h 有序数组
一个数组是 h 有序的，是指这个数组中任意间隔为 h（或者说间隔元素的个数为 h-1）的元素都是有序的。
例如 h=3 时，一个 3 有序数组意味着：
- 所有下标为 0, 3, 6, 9... 的元素有序
- 所有下标为 1, 4, 7, 10... 的元素有序
- 所有下标为 2, 5, 8, 11... 的元素有序
算法思想
希尔排序通过对数组进行预处理（使其变成 h 有序数组），增加数组的局部有序性，从而让后续的插入排序更加高效。
算法可视化：
与类似概念对比
| 维度 | 希尔排序 | 插入排序 | 选择排序 |
|---|---|---|---|
| 时间复杂度 | 取决于间隔序列 | O(n²) | O(n²) |
| 空间复杂度 | O(1) | O(1) | O(1) |
| 稳定性 | ❌ 不稳定 | ✅ 稳定 | ❌ 不稳定 |
| 是否原地 | ✅ 是 | ✅ 是 | ✅ 是 |
| 突破 O(n²) | ✅ 是 | ❌ 否 | ❌ 否 |
时间复杂度/性能
| 场景 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | 取决于间隔序列 | 不同间隔序列表现不同 |
| 最坏情况 | O(n²) | 某些间隔序列的最坏情况 |
| 平均情况 | O(n^1.3)~O(n^1.5) | 取决于间隔序列选择 |
注意事项
- 间隔序列选择：不同的间隔序列（gap sequence）对性能影响很大
- 不稳定：由于间隔交换，相同元素的相对位置可能改变
- 预处理的重要性：h 有序数组的预处理是性能提升的关键
经典算法
相关概念
待补充
由于原文不完整（在"Loading comments..."处截断），以下内容缺失：
- h 有序数组的完整示例和图示
- 希尔排序的完整算法步骤
- 间隔序列（gap sequence）的具体选择和实现
- 完整的时间复杂度分析证明
- 代码实现
- 与快速排序、归并排序等高级排序算法的对比
如需完整内容，请手动复制原文后重新摄取。