希尔排序详解
目录
一、从直接插入排序到希尔排序的优化思想
📌 什么是局部有序？
二、核心优化思想：预排序
三、gap分组思想
📌 基本思想：
📌 示例过程
gap = 4
gap = 2
gap = 1
四、希尔排序代码实现（优化版本）
五、代码核心思想解析
📌 1. gap控制分组
📌 2. 分组处理
📌 3. 组内插入排序
六、希尔排序时间复杂度分析
📌 常见结论（经验统计）
✔ 平均时间复杂度O(n^1.3)
✔ 最坏情况O(n^2)
✔ 空间复杂度O(1)
七、算法本质总结
一、从直接插入排序到希尔排序的优化思想
在学习直接插入排序时我们知道，它在数据基本有序的情况下效率很高，但在完全无序甚至逆序的情况下性能较差，其时间复杂度通常为：O(n^2)
但如果数据越接近“局部有序”，插入排序的效率会显著提升，甚至接近：O(n)
📌 什么是局部有序？
所谓局部有序，指的是：
- 小的元素大致靠前
- 大的元素大致靠后
- 中间元素分布相对合理
例如一个数组虽然整体无序，但如果：
- 前半部分整体较小
- 后半部分整体较大
那么它就比完全逆序更接近有序状态。
二、核心优化思想：预排序
既然插入排序对“接近有序”的数据效率更高，那么我们可以：
在正式排序之前，先让数据“变得更有序”
这个过程就叫：
预排序（Pre-Sorting）
三、gap分组思想
希尔排序的核心是引入一个间隔变量gap：
📌 基本思想：
- 将数组按 gap 分成若干组
- 每组内部进行插入排序
- 不断缩小 gap
- 最终 gap = 1 时完成整体排序
📌 示例过程
假设初始数组：
[15, 7, 3, 11, 1, 9, 5, 13]gap = 4
分组：
- (15,1)
- (7,9)
- (3,5)
- (11,13)
组内排序后：
[1, 7, 3, 11, 15, 9, 5, 13]gap = 2
分组：
- (1,3,15,5)
- (7,11,9,13)
进一步接近有序
gap = 1
直接插入排序完成最终排序
希尔排序动图：
四、希尔排序代码实现（优化版本）
下面是基于“分组插入排序思想”的实现：
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { // gap递减策略（保证最终为1） gap = gap / 3 + 1; // 对每一组分别进行插入排序 for (int j = 0; j < gap; j++) { for (int i = j; i < n - gap; i += gap) { int end = i; int tmp = a[end + gap]; // 组内插入排序 while (end >= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } } }五、代码核心思想解析
📌 1. gap控制分组
gap = gap / 3 + 1;作用：
- 逐步缩小分组规模
- 最终一定收敛到 gap = 1
- 保证最后进行一次完整插入排序
📌 2. 分组处理
for (int j = 0; j < gap; j++)含义：
将数组划分为 gap 个子序列
例如 gap = 4：
0,4,8,... 1,5,9,... 2,6,10,... 3,7,11,...📌 3. 组内插入排序
for (int i = j; i < n - gap; i += gap)在同一组内按间隔 gap 进行插入排序
六、希尔排序时间复杂度分析
希尔排序的时间复杂度与 gap 序列密切相关，目前尚无统一精确结论。
📌 常见结论（经验统计）
✔ 平均时间复杂度O(n^1.3)
✔ 最坏情况O(n^2)
✔ 空间复杂度O(1)
七、算法本质总结
希尔排序可以总结为一句话：
通过 gap 分组不断优化数据结构，使插入排序在接近有序的数据上运行