【数据结构与算法】希尔排序
👨💻 关于作者：会编程的土豆
“不是因为看见希望才坚持，而是坚持了才看见希望。”
你好，我是会编程的土豆，一名热爱后端技术的Java学习者。
📚 正在更新中的专栏：
- 《数据结构与算法》😊😊😊
- 《leetcode hot 100》🥰🥰🥰🤩🤩🤩
- 《数据库mysql》
💕作者简介：后端学习者
概念
希尔排序 = 插入排序 + 分组跳跃
它不是一次只和前面相邻的元素比，而是先隔着很远比，然后慢慢缩小距离，最后变成普通的插入排序
为什么需要希尔排序？
简单插入排序有个明显的软肋：当较小的数都堆在数组尾部时，排序效率会很低。因为插入排序每次只能交换相邻元素，要把尾部的小数挪到前面，需要一步一步“冒泡”过去，非常耗时。
看一下插入排序的代码：
public static void insertionSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { int j = i; int temp = arr[j]; while (j > 0 && arr[j - 1] > temp) { //如果前一个元素比当前元素大，则将前一个元素向后移动一位。 //将 j 的值减1，继续比较前一个元素。 arr[j] = arr[j - 1]; j--; } arr[j] = temp; } } 而希尔排序通过引入增量（Gap）的概念，允许元素跳跃式移动，让小数能更快地“蹦”到前面，从而解决了这一问题
希尔排序代码
void shellSort(vector<int>& arr) { int n = arr.size(); // 外层循环：控制 gap 从 n/2 开始，每次减半 for (int gap = n / 2; gap > 0; gap /= 2) { // 内层循环：对每个分组做插入排序 // 注意这里从 gap 开始，而不是从 1 开始 for (int i = gap; i < n; ++i) { int key = arr[i]; int j = i - gap; // 和前面相隔 gap 的元素比较 while (j >= 0 && arr[j] > key) { arr[j + gap] = arr[j]; // 大的往后挪 gap 个位置 j -= gap; // 往前跳 gap 个位置继续比 } arr[j + gap] = key; // 插入到正确位置 } } }插入排序 vs 希尔排序 代码对比
| 插入排序 | 希尔排序 |
|---|---|
for (int i = 1; i < n; ++i) | for (int gap = n/2; gap > 0; gap/=2) |
for (int i = gap; i < n; ++i) | |
int j = i - 1; | int j = i - gap; |
while (j >= 0 && arr[j] > key) | while (j >= 0 && arr[j] > key) |
arr[j + 1] = arr[j]; | arr[j + gap] = arr[j]; |
j -= 1; | j -= gap; |
arr[j + 1] = key; | arr[j + gap] = key; |
唯一的区别：把插入排序里的 1 全部换成了 gap，再套一层 gap 递减的循环。
复杂度与特点
| 特性 | 说明 |
|---|---|
| 时间复杂度 | 取决于 gap 序列，经典希尔增量 O(n²)，优化序列可达 O(n^1.3) |
| 空间复杂度 | O(1)，原地排序 |
| 稳定性 | 不稳定（跳跃式交换可能打乱相同元素的顺序） |
| 适用场景 | 中等规模数据，嵌入式设备等内存敏感场景 |
一句话总结
希尔排序 = 带间隔的插入排序，通过"大步跳跃 + 逐步逼近"来优化小数后移的问题。
希尔排序的核心原理
核心概念：增量（Gap）
希尔排序引入了一个间隔 gap，它不是让元素和相邻的比，而是和相隔 gap 个位置的元素比。
过程分三步：
- 分组：按 gap 把数组分成若干组
- 组内插入排序：对每组分别做插入排序
- 缩小 gap：gap 减半，重复上述过程，直到 gap = 1
当 gap = 1 时，就是普通的插入排序，但此时数组已经基本有序，插入排序会非常快。
图解演示
数组：[80, 93, 60, 12, 42, 30, 68, 85, 10]
第一轮：gap = 4
把相隔 4 个位置的元素分为一组：
下标: 0 1 2 3 4 5 6 7 8 值: 80 93 60 12 42 30 68 85 10 分组情况（相同标记的为一组）： 组1 (▲): 80, 42, 10 → 下标 0, 4, 8 组2 (●): 93, 30 → 下标 1, 5 组3 (■): 60, 68 → 下标 2, 6 组4 (◆): 12, 85 → 下标 3, 7对每组分别做插入排序：
- 组1 排序后：10, 42, 80
- 组2 排序后：30, 93
- 组3 排序后：60, 68
- 组4 排序后：12, 85
放回原数组：
排序前: [80, 93, 60, 12, 42, 30, 68, 85, 10] 排序后: [10, 30, 60, 12, 42, 93, 68, 85, 80]观察：最小的 10 从最后一位（下标 8）跳到了第一位（下标 0）！一步跨了 8 个位置，这就是希尔排序的效率来源。
第二轮：gap = 2
当前: [10, 30, 60, 12, 42, 93, 68, 85, 80] 分组： 组1 (▲): 10, 60, 42, 68, 80 → 下标 0,2,4,6,8 组2 (●): 30, 12, 93, 85 → 下标 1,3,5,7分别插入排序后放回：
排序前: [10, 30, 60, 12, 42, 93, 68, 85, 80] 排序后: [10, 12, 42, 30, 60, 85, 68, 93, 80]第三轮：gap = 1
就是普通的插入排序：
排序前: [10, 12, 42, 30, 60, 85, 68, 93, 80] 排序后: [10, 12, 30, 42, 60, 68, 80, 85, 93]此时数组已经基本有序，插入排序只需要很少的移动就能完成。
注意排序时：
每一组元素只在属于自己组的下标位置之间进行排序和交换，完全不碰其他组的元素。
说人话就是：比如说这一组数，就是在原来数组的这一组的基础之上排序换位置，而其他组的位置丝毫不影响，只在自己的那个gap组里面换；
