希尔排序（Shell Sort）是插入排序的优化版本，通过 “分组插入排序 + 逐步缩小步长” 的策略，大幅降低插入排序在无序数组中的时间开销。它摒弃了插入排序 “逐个比较” 的低效性，先通过大跨度分组让数组 “基本有序”，再用插入排序收尾，是理解 “增量排序” 思想的关键算法，也是面试中常考的进阶排序考点。
一、希尔排序是什么？
希尔排序的核心是 “步长（增量）”—— 将数组按步长 gap 划分为多个子数组，对每个子数组单独做插入排序；逐步缩小步长（通常减半），直到步长为 1，此时数组已基本有序，最后一次插入排序即可快速完成整体排序。
核心思想：
选步长：初始步长通常为数组长度的一半（gap = n/2）；
分组排序：按步长 gap 将数组分为 gap 组，每组内做插入排序；
缩步长：步长减半（gap = gap/2），重复分组排序；
收尾：当步长为 1 时，执行一次普通插入排序，完成最终排序。
效率与特性：
时间复杂度：O(n^1.3) ~ O(n²)（取决于步长序列，优于插入排序的 O (n²)）
空间复杂度：O(1)（原地排序，无额外空间消耗）
排序特性：不稳定排序（分组排序会打乱相等元素相对位置）、原地排序
适用场景：
适合中等规模数据排序，是插入排序的高效替代方案；无需稳定性的场景下，性能优于基础排序算法。
二、核心实现方式（经典步长版）
希尔排序的核心是 “按步长分组插入”，以下是最易理解的经典实现，适配新手入门：
import java.util.Arrays;
public class ShellSort {
/**
* 希尔排序入口（升序）
* @param arr 待排序数组
*/
public static void shellSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 1. 初始化步长为数组长度的一半，逐步减半至1
for (int gap = n / 2; gap > 0; gap /= 2) {
// 2. 按步长分组，对每组执行插入排序
// 从gap开始遍历，每个元素作为待插入元素
for (int i = gap; i < n; i++) {
// 缓存待插入元素（避免后移覆盖）
int insertVal = arr[i];
// 已排序区间的前一个元素下标（同组内）
int j = i - gap;
// 3. 同组内向前找插入位置，元素按步长后移
while (j >= 0 && arr[j] > insertVal) {
arr[j + gap] = arr[j]; // 元素后移gap位
j -= gap; // 继续向前找同组元素
}
// 4. 放入待插入元素
arr[j + gap] = insertVal;
}
}
}
// 调用示例
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 7, 6, 1, 8, 4};
shellSort(arr);
System.out.println(Arrays.toString(arr)); // 输出[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
三、必避的三个核心坑
希尔排序的核心难点在 “步长控制” 和 “分组插入逻辑”，新手易踩这些关键坑：
1、步长终止条件： 步长循环需保证 gap > 0，而非 gap >= 0，否则步长为 0 时会导致数组下标越界；
2、分组插入边界： 内层 while 循环需加 j >= 0 条件，避免遍历到数组头部时下标越界；
3、稳定性问题： 希尔排序天生不稳定（如数组 [3, 2, 3]，步长 2 时分两组 [3,3] 和 [2]，排序后两个 3 的相对位置可能改变），切勿用于对稳定性有要求的场景。
四、总结
1、希尔排序核心逻辑是 “按步长分组插入排序，逐步缩步长至 1”，通过分组让数组快速接近有序，大幅优化插入排序效率；
2、希尔排序是原地、不稳定排序，时间复杂度优于基础插入排序，适合中等规模数据排序；
3、核心避坑点是控制步长终止条件、保证分组插入的边界安全，明确其 “不稳定” 的特性，避免误用在对元素相对位置有要求的场景。
