企业官网建设流程全解析

直接插入排序、折半插入排序、希尔排序，这三个名字放在一起，足够让刚开始学数据结构的人挠头：明明都叫插入排序，为什么有的稳定有的不稳定？为什么折半插入排序听起来高级，时间复杂度却还是 O(n²)？希尔排序一趟趟分组到底在干嘛？我在带新人、面试候选人的时候也发现，能把这三种排序逻辑讲透的人并不多。这篇文章就把它们放在一起彻底拆开，从思想到代码、从手算到复杂度，一条线讲明白。适合刚学排序的学生，也适合准备算法面试、想快速激活记忆的工程师。

1. 先认识插入排序这一家子

1.1 为什么一定要学插入排序

排序算法那么多，快排、归并、堆排各自都有非常优秀的平均复杂度，但绝大部分教材依然把插入排序放在最前面讲。因为它承担着“算法优化这条路怎么走”的教学任务。从直接插入排序到折半插入排序再到希尔排序，你看到的不是三个孤立算法，而是一条非常清晰的优化链：先解决“能不能排好”，再解决“能不能少比较”，最后解决“能不能少移动”。这种思路迁移到字符串匹配、动态规划等很多领域都是一样有效的。

而且插入排序本身并不“鸡肋”。数据量在几十这个量级、或者数据已经几乎有序的场景下，直接插入排序的常数因子非常小，实测往往比快速排序还要快。很多成熟语言的内置排序都会在小区间切到插入排序，这可不是什么陌生的黑科技，而是实打实的工程基础。对面试来说，手写一个直接插入排序甚至可能只是热身，后面跟着的复杂度分析、稳定性判断、优化思路才是真正拉开差距的地方。

1.2 三种插入排序是同一思路的两层进化

先给这一家子排个辈分：

• 直接插入排序：每次取未排序区第一个元素，在已排序区从后往前找位置插入。
• 折半插入排序：在直接插入的基础上，把“从后往前逐个比较”改成“二分查找定位”。
• 希尔排序：先用较大增量分组，组内做直接插入排序；然后不断缩小增量，最终增量为 1 时完成整体插入排序。

你可以把它们看作三个版本：第一版最原始，第二版优化了“找位置”环节，第三版优化了“整体搬移”环节。先记住这条进化链，后面每个细节都会好理解得多。很多同学一上来就背分层代码，结果越背越混，根源就在于没有抓住这条主线。后面每一章的代码和手算过程，我都会尽量贴着这条主线讲。

2. 直接插入排序：一张一张把牌插进手牌

2.1 核心思想：维护“已排序前缀”

想象你打扑克时起牌，左手已经抓了一叠牌，而且始终是从小到大排列的。新摸到一张牌，你做的事其实只有两步：从右往左看这张牌应该插在哪个位置；把比它大的牌一张张往右挪，腾出空位再放进去。

这正是直接插入排序的全部逻辑。数组被看成一个“已排序前缀 + 未排序后缀”的结构。初始状态就是第一个元素自己构成已排序前缀，因为单个元素必然有序。之后每轮取未排序部分的第一个元素，把它插入到前缀的合适位置，前缀长度就加一。循环 n-1 轮，整个数组有序。

2.2 全过程手算：从 9 3 7 1 5 4 2 8 6 出发

我习惯用一组随机一点的数据做演示，比如 arr = {9, 3, 7, 1, 5, 4, 2, 8, 6}。为了看得清楚，我用“|”隔开已排序部分和未排序部分：

• 初始：9 | 3 7 1 5 4 2 8 6
• 第1趟：temp=3，9 后移，插入到最前面 → 3 9 | 7 1 5 4 2 8 6
• 第2趟：temp=7，9 后移，7 插到 3 和 9 之间 → 3 7 9 | 1 5 4 2 8 6
• 第3趟：temp=1，9、7、3 全部后移，1 到最前 → 1 3 7 9 | 5 4 2 8 6
• 第4趟：temp=5，9 后移、7 后移，5 插到 3 和 7 之间 → 1 3 5 7 9 | 4 2 8 6
• 第5趟：temp=4，9、7、5 依次后移，4 插到 3 和 5 之间 → 1 3 4 5 7 9 | 2 8 6
• 第6趟：temp=2，9、7、5、4、3 依次后移，2 插到 1 和 3 之间 → 1 2 3 4 5 7 9 | 8 6
• 第7趟：temp=8，9 后移，8 插到 7 和 9 之间 → 1 2 3 4 5 7 8 9 | 6
• 第8趟：temp=6，9、8、7 依次后移，6 插到 5 和 7 之间 → 1 2 3 4 5 6 7 8 9

每一趟结束，已排序前缀正好增加一个元素。你会发现这很像一波一波地在已排序序列里“插入新牌”，过程没有任何跳跃，所以算法本身非常直观。

2.3 代码实现：循环边界的理解

代码很短，但循环条件是重灾区：

public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } }

有两个细节我每次都会强调。第一，while 里必须保留 j >= 0 的判断，否则 j 会一路减到 -1，再访问 arr[j] 就越界了。第二，比较要写 arr[j] > temp，不是 >=。如果写成 >=，那么当待插入元素和已排序区某个元素相等时，它会被插到这个相等元素的前面，两个相同元素的相对顺序就被颠倒了，排序就变得不稳定。直接插入排序本来可以做到稳定，很多人写出来的版本却写成了不稳定，多半就是栽在这里。

这里还想再强调一次：while 条件里必须先判断 j >= 0，再比较 arr[j] 与 temp。顺序不能反过来，否则 j 已经变成 -1 时还要去取 arr[j] 就直接越界报错了。

2.4 复杂度推导：比较和移动哪个拖后腿

最乐观的情况，数组已经是升序。此时每轮只需做一次比较，发现 arr[j] <= temp，直接结束，不需要任何移动，所以最好时间复杂度是 O(n)。

最悲观的情况，数组完全逆序。第 i 轮需要比较 i 次、移动 i 次，总和大约是 1+2+...+n-1 = n(n-1)/2，所以最坏时间是 O(n²)。平均情况同样落在 O(n²)。空间方面，只使用了一个 temp 临时变量，所以空间复杂度是 O(1)。

再点一句：插入排序的移动次数本质上等于数组的“逆序对数量”。如果一个数据接近有序，逆序对少，插入排序就跑得飞快；如果数据乱成一锅粥，逆序对接近 n²/2，它就跑得很难看。这一条特性会直接决定我们后面为什么要设计希尔排序。

3. 折半插入排序：把顺序查找换成二分查找

3.1 优化点：只省比较，不省移动

直接插入排序在找插入位置时，是从已排序区尾部一个一个往前比。如果前缀很长，比较次数就很多。但前缀本身是有序的，有序数组找位置，天然适合二分查找。

折半插入排序把“逐个比较找位置”换成“二分查找找位置”，每一轮找插入点的比较次数从最多 i 次降到最多 log₂(i) 次。听起来很理想，但注意：元素找到位置之后，照样需要把比它大的那些元素整体后移，这部分移动成本没有任何变化。所以折半插入排序真正省掉的是“比较次数”，而不是“移动次数”。

3.2 二分定位的关键边界条件

二分定位的边界条件容易写错，我这里直接给一个同时保证正确和稳定的写法：

while (low <= high) { int mid = (low + high) >>> 1; if (arr[mid] <= temp) { low = mid + 1; } else { high = mid - 1; } }

循环结束时，low 就是要插入的位置。这里最容易被忽视的细节是：当 arr[mid] == temp 时，应该走 low = mid + 1，而不是 high = mid - 1。为什么要这样？为了让新元素插入到等于它的元素后面。如果写成“只有小于才让 low 前移”，等于的时候往左半区走，最终插入位置会落在第一个等于 temp 的元素前面，原来在前面的相等元素反而被排到了后面，稳定性就没了。所以这个 <= 是稳定性的保障，不是可有可无的细节。

3.3 手算演示：temp=5 到底插在哪

还是用 arr = {9, 3, 7, 1, 5, 4, 2, 8, 6}。前几轮的结果和直接插入排序完全一样，到第4轮时，已排序部分是 1 3 7 9，待插入 temp=5。这时二分查找过程是：

low=0, high=3, mid=1，arr[1]=3 <= 5，所以 low=2； low=2, high=3, mid=2，arr[2]=7 > 5，所以 high=1；

现在 low=2, high=1，low > high，循环结束，插入位置就是 low=2。然后把 7 和 9 分别后移一位，把 5 放到索引 2，得到 1 3 5 7 9。和直接插入排序的结果一模一样，只是“找位置”的方式从逐个比较换成了二分。后面的每轮都重复同样的逻辑，最终结果当然也是有序的。

3.4 复杂度与稳定性：别被“二分”骗了

折半插入的“找位置”成本确实降到了 O(log n) 每轮，整个排序的比较次数合计约为 O(n log n)。但移动次数在最坏情况下仍然是 n(n-1)/2 这个量级，所以总体最坏、平均时间复杂度依然是 O(n²)。很多初学者以为改了个二分就变成 O(n log n) 了，这是最常见的认知误区。

最好的情况要单独说明：如果数据已经完全有序，每轮移动次数为 0，只剩二分查找的比较开销，所以最好复杂度是 O(n log n)。不过大多数教材会直接笼统标一个 O(n²)，面试时你按“最坏 O(n²)”答是安全的，但心里要知道“最好 O(n log n)”这句话也不算错。稳定性方面，只要二分条件写成 arr[mid] <= temp，它就是稳定的。空间复杂度 O(1)。

4. 希尔排序：先宏观有序，再微观有序

4.1 为什么插入排序适合“基本有序”的数据

从直接插入排序的复杂度分析能看出来，它最怕逆序对很多的数组，因为每插一个元素都要移动一堆数据。反过来，如果数组“大体有序”，只有少数元素乱序，插入排序几乎只需要做线性次操作。

希尔排序的思路就是：先想办法让数组变得“大体有序”，再交给插入排序收尾。怎么让数组大体有序？答案是分组。不是简单分成几段，而是按间隔取元素分成若干子序列，先对每个子序列做插入排序。这样做可以快速把一些相隔很远的元素移动到大致正确的位置，大幅减少后续整体插入时的移动量。随着间隔不断缩小，子序列规模越来越大，直到间隔为1，整个数组合并成完整序列，排序完成。所以希尔排序也叫“缩小增量排序”。

4.2 分组策略与增量序列的选择

“间隔”在希尔排序里叫增量，一般用 gap 表示。增量序列是整个算法的灵魂。最简单也最常用的策略是：gap 初始取 n/2，然后每趟 gap = gap / 2，一直缩到 1。比如 n=9 时，gap 依次取 4、2、1。这个策略写起来简单，理解起来直观，是教学和笔试的首选。

还有若干更复杂的增量序列，可以把最坏复杂度进一步压低。比如取形如 2^k - 1 的增量，最坏可以达到 O(n^(3/2)) 左右；再进化一些的增量组合甚至可以压到 O(n^(4/3)) 量级。但工程上老老实实用 gap = n/2 往下折半的情况非常多，因为实现简单、常数小，面对绝大多数实际数据已经足够快。面试时能说出“增量序列会影响希尔排序的复杂度”这一点，已经比很多人强了。

4.3 全过程手算：gap=4 → 2 → 1

还是用那一组数据演示。arr = {9, 3, 7, 1, 5, 4, 2, 8, 6}，n=9。

先看 gap=4。数组被分成4组，每组内下标相差4：

• 组1：下标0、4、8，元素 9、5、6，插入排序后变成 5、6、9；
• 组2：下标1、5，元素 3、4，保持 3、4；
• 组3：下标2、6，元素 7、2，变成 2、7；
• 组4：下标3、7，元素 1、8，保持 1、8。

这一趟之后数组变成：5 3 2 1 6 4 7 8 9。注意，大的数字已经明显往右边靠了，但还未完全有序。

接下来 gap=2，分成两组：

• 组1：下标0、2、4、6、8，元素 5、2、6、7、9，插入排序后变成 2、5、6、7、9；
• 组2：下标1、3、5、7，元素 3、1、4、8，插入排序后变成 1、3、4、8。

这一趟之后数组变成：2 1 5 3 6 4 7 8 9。

最后 gap=1，直接对整个数组做依次插入排序，过程其实就是前面的直接插入排序：2 1 5 3 6 4 7 8 9 → 1 2 3 4 5 6 7 8 9。三趟搞定。对比直接插入排序需要八趟，希尔排序的“宏观先调”优势在这里非常明显。

4.4 代码实现：为什么内层循环写成那样

希尔排序的经典代码长这样：

public static void shellSort(int[] arr) { if (arr == null || arr.length < 2) { return; } int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > temp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = temp; } } }

很多初学者不理解为什么内层循环不是“先按组分好，再一组一组排”，而是从 i=gap 往后一个个处理。其实这两种写法是等价的：当 i 从 gap 扫描到 n-1 时，每个元素都在它自己所在的组里，向前按 gap 步长做插入；而同一组中位置更靠前的元素已经在更早的迭代中被处理过了，于是组内顺序被逐步维护起来。这种写法的好处是省去了分组带来的额外存储，所有交换和移动都在原数组内完成，空间复杂度保持 O(1)。

4.5 稳定性分析：用反例说明希尔排序不稳定

希尔排序是不稳定的。这几乎是所有资料的标准结论，但很多人没想明白为什么。我给一个最直观的反例。

数组：5、5、5、1。为了区分三个相等的5，我把它们记为 5a、5b、5c，初始顺序是 5a(下标0)、5b(下标1)、5c(下标2)、1(下标3)。

取 gap=2。分组为：

• 组1：5a、5c，插入排序后保持不变；
• 组2：5b、1，插入排序后变成 1、5b。

第一趟结束数组变成：5a、1、5c、5b。到这里已经能看出问题：5b 被移动到了整个数组的末尾。

接着 gap=1 做直接插入排序：1 被插到最前面；5c、5b 依次与前面的 5a 比较，但都不小于 5a，所以位置不再变化。最终顺序为：5a、5c、5b、1。原来的顺序是 5a、5b、5c，现在 5b 和 5c 的相对位置颠倒了，所以希尔排序不稳定。

深一层想：直接插入排序每个子序列内部是稳定的，但不同子序列的元素会在后续增量排序中跨越移动，跨越之后没有任何机制能保证相等元素的原有相对次序，于是整体稳定性就被破坏了。这也是为什么很多需要稳定排序的业务场景不敢轻易用希尔排序。

5. 三种插入排序横向对比与工程选型

5.1 一张表看穿复杂度、稳定性和场景

为了便于记忆，我把三种插入排序放在一张表里：

这张表有两点要特别提醒。第一，折半插入那一行的“O(n log n)”指的是最好情况，别拿去答“平均复杂度”，面试官问平均复杂度时标准答案依然是 O(n²)。第二，希尔排序的平均复杂度在业界和学术界没有一个非常统一的固定值，它和增量序列强相关，常规折半增量下实测基本是介于 O(n^1.3) 和 O(n²) 之间，回答时强调“依赖增量选择”比硬背一个数字更准确。

5.2 面试高频考点与常见误区

面试里关于这三种排序的问题，翻来覆去就那么几个：

1. 手写直接插入排序，并说明稳定性。
2. 折半插入排序比直接插入排序优化了什么？复杂度为什么仍然是 O(n²)？
3. 希尔排序为什么不稳定？增量序列有什么影响？
4. 三种排序分别适合什么场景？

与之相伴的还有几个非常经典的误区。第一个误区是“折半插入是 O(n log n)”，错在只看比较不看移动。第二个误区是“希尔排序的 gap 随便选”，其实增量选得不好会让性能退化到接近 O(n²)。第三个误区是“排序算法只要结果对就行”，希尔排序就是活生生的反例，它会让相等元素顺序变化，需要稳定排序的场合直接不能用。第四个误区是“用排序必须上最优算法”，其实工程里小数据量下插入排序的常数优势和缓存友好性，往往比复杂排序更实用。

5.3 工程里到底选哪个

工作中很少有人让你基于一个几百万条数据的数组去手写排序，因为语言标准库里的排序已经足够好。但在数据规模小、或者数据基本有序的场景里，插入排序的“低常数”优势会非常突出，很多主流语言的排序实现都会在小区间切换到插入排序，这个细节经常被忽略。

如果允许我给出一个实用建议：数据量在几十条以内、几乎有序、或者需要稳定排序，优先考虑直接插入排序；如果只想要“稳定”但希望比较次数少一点，可以用折半插入排序，但要清楚移动成本还在；如果数据量到了几千、几万，不要求稳定，又希望代码简单、常数小，希尔排序是一个性价比很高的中间选择。再大规模的数据，就交给快速排序、归并排序或堆排序去处理。

6. 常见问题与排查技巧实录

6.1 越界与死循环问题

写这三种排序最常见的翻车现场，集中在循环边界上。直接插入排序里，while (j >= 0 && arr[j] > temp) 如果漏掉 j >= 0，当 temp 比已排序区所有元素都小时，j 会跑到 -1，下一轮访问 arr[-1] 直接抛异常。希尔排序的 while 循环也是一样，只是把 j-- 换成了 j -= gap，越界风险更容易被忽略。折半插入排序则容易在“等于”时走错分支，导致结果不正确或排序不稳定。

我的排查习惯是：写完之后先用一组随机小数组跑一遍，再用一组包含大量重复元素的数组跑一遍，打印每一趟结果。前者验证功能，后者验证稳定性，两分钟就能发现问题。

6.2 测试步骤与稳定性验证方法

验证排序正不正确，最简单的办法是排完后遍历一遍确认相邻元素非降序。但这个验证不了稳定性。要验证稳定，可以给数组元素带上原始下标，比如把 (值, 原始下标) 封装成对象再排序，排序结束后检查相同值的对象是否还保持下标递增。这个方法我在教算法时反复推荐，比肉眼看一组数字可靠得多。

如果你身边没有现成的测试框架，直接用一段简单的代码就行：定义一个小类型，包含 value 和 index 两个字段，按 value 排序结束后，遍历并确认“value 相等的元素，index 一定递增”。有了这个验证器，直接插入排序和折半插入排序能通过，希尔排序大概率会在某些用例上失败。这也能帮你直观理解稳定性到底是怎么被破坏的。

6.3 我的一点习惯和结论

我自己写排序代码时有个习惯：所有涉及二分的地方，一律用 (low + high) >>> 1 求中间位置。这个写法在 low + high 很大的时候不会发生整数溢出，比 (low + high) / 2 更稳。另外，只要涉及排序稳定性，我写比较条件时都会刻意写成“严格大于才交换”，这样潜意识里就避免了把稳定排序写崩。

三种插入排序看起来只是三个小算法，但它们背后的优化链条很值得反复琢磨：先能用，再少比较，再少搬移。把这层逻辑吃透，后面学快速排序的基准选择、归并排序的分治合并，都会感觉顺很多。

最后再分享一个我带过的学生们普遍反馈有效的方法：学这块内容，先别急着打开编辑器，拿一副扑克牌按这三种策略各手动插一遍。直接插入就是一张张往手里插，折半插入就是在手牌里猜中间位置然后决定插左边还是右边，希尔排序就是先把牌隔几张分成几叠，每叠理好再逐步缩小间隔。亲手走过几遍之后，再看代码里的循环条件会顺很多。这个习惯我到现在都还在用，也希望你能试试。