希尔排序是插入排序的改进算法，通过分组插入与逐步缩小间隔（gap）使数组渐进有序，最终以gap=1完成插入排序；核心在于gap序列选择，而非直接优化插入排序本身。
希尔排序不是插入排序的“优化版”，而是插入排序的一种改进思路——它通过分组和逐步缩小间隔，让数组更快接近有序状态，从而大幅降低后续插入排序的移动次数。直接说“用希尔排序优化插入排序”容易误解；准确讲，希尔排序 = 分组插入排序的多次执行，核心在于间隔序列（gap sequence）的选择。
理解希尔排序的本质逻辑
普通插入排序在近乎有序时效率高（O(n)），但面对完全乱序数组，最坏达 O(n²)。希尔排序先用较大间隔把数组分成若干子序列，对每个子序列做插入排序；随着间隔不断缩小，整体数据越来越有序，最后一次间隔为 1 时，就是对几乎有序数组做一次插入排序，效率显著提升。
关键不在于“改插入排序”，而在于控制比较和移动的粒度：大间隔 → 快速粗调位置；小间隔 → 精细修正顺序。
常用间隔序列与实现要点
间隔序列直接影响性能。推荐使用 Knuth 序列：gap = gap * 3 + 1（生成：1, 4, 13, 40…），然后倒序使用；或更简洁的 Shell 原始序列（n/2, n/4, …, 1）。避免使用 2^k 序列（如 8,4,2,1），它存在已知的最坏情况缺陷。
立即学习“Java免费学习笔记（深入）”；
- 先计算初始 gap：从 1 开始循环生成，直到 gap ≥ 数组长度，再除以 3 回退一步
- 外层循环按 gap 递减，内层对每个子序列（从 gap 开始，步长为 gap）执行插入排序
- 子序列插入排序写法与普通插入排序一致，只是比较和移动索引差为 gap
Java 示例代码（Knuth 序列）
// 升序排列
public static void shellSort(int[] arr) {
int n = arr.length;
// 生成最大 gap（Knuth 序列）
int gap = 1;
while (gap < n / 3) gap = gap * 3 + 1;
<pre class="brush:php;toolbar:false;">while (gap >= 1) {
// 对每个子序列执行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap /= 3; // 缩小间隔
}}
为什么比纯插入排序快？
假设数组 [64, 34, 25, 12, 22, 11, 90]：
- 纯插入排序：最小元素 11 需要向左移动 6 次才能到位
- 希尔排序（gap=4）：先排 [64,22], [34,11], [25,90], [12] → 11 已提前到索引 1；gap=1 时只需少量调整
- 本质是减少长距离元素迁移的总次数，尤其对逆序较多的数组效果明显
平均时间复杂度约 O(n^1.3)，虽不如快排或归并，但原地、稳定（若插入排序稳定）、且对中等规模数据（几千以内）常有不错表现。
