概念
希尔排序 = 插入排序 + 分组跳跃
它不是一次只和前面相邻的元素比，而是先隔着很远比，然后慢慢缩小距离，最后变成普通的插入排序。
为什么需要希尔排序？
简单插入排序有个明显的软肋：当较小的数都堆在数组尾部时，排序效率会很低。因为插入排序每次只能交换相邻元素，要把尾部的小数挪到前面，需要一步一步'冒泡'过去，非常耗时。
看一下插入排序的代码逻辑：
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) {
// 如果前一个元素比当前元素大，则将前一个元素向后移动一位
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
而希尔排序通过引入增量（Gap）的概念，允许元素跳跃式移动，让小数能更快地'蹦'到前面，从而解决了这一问题。
核心原理
核心概念：增量（Gap）
希尔排序引入了一个间隔 gap，它不是让元素和相邻的比，而是和相隔 gap 个位置的元素比。
过程分三步：
- 分组：按 gap 把数组分成若干组
- 组内插入排序：对每组分别做插入排序
- 缩小 gap：gap 减半，重复上述过程，直到 gap = 1
当 gap = 1 时，就是普通的插入排序，但此时数组已经基本有序，插入排序会非常快。
代码实现
public static void shellSort(int[] arr) {
int n = arr.length;
// 外层循环：控制 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 = 1; i < n; ++i) | 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 递减的循环。
图解演示
数组：[80, 93, 60, 12, 42, 30, 68, 85, 10]
第一轮：gap = 4
把相隔 4 个位置的元素分为一组：
- 组 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 组里面换。
复杂度与特点
| 特性 | 说明 |
|---|---|
| 时间复杂度 | 取决于 gap 序列，经典希尔增量 O(n²)，优化序列可达 O(n^1.3) |
| 空间复杂度 | O(1)，原地排序 |
| 稳定性 | 不稳定（跳跃式交换可能打乱相同元素的顺序） |
| 适用场景 | 中等规模数据，嵌入式设备等内存敏感场景 |
一句话总结：希尔排序 = 带间隔的插入排序，通过"大步跳跃 + 逐步逼近"来优化小数后移的问题。
