插入排序三兄弟：直接插入、折半插入、希尔排序全解析

直接插入排序、折半插入排序、希尔排序这三个名字放在一起足够让刚开始学数据结构的人挠头明明都叫插入排序为什么有的稳定有的不稳定为什么折半插入排序听起来高级时间复杂度却还是 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趟temp39 后移插入到最前面 → 3 9 | 7 1 5 4 2 8 6第2趟temp79 后移7 插到 3 和 9 之间 → 3 7 9 | 1 5 4 2 8 6第3趟temp19、7、3 全部后移1 到最前 → 1 3 7 9 | 5 4 2 8 6第4趟temp59 后移、7 后移5 插到 3 和 7 之间 → 1 3 5 7 9 | 4 2 8 6第5趟temp49、7、5 依次后移4 插到 3 和 5 之间 → 1 3 4 5 7 9 | 2 8 6第6趟temp29、7、5、4、3 依次后移2 插到 1 和 3 之间 → 1 2 3 4 5 7 9 | 8 6第7趟temp89 后移8 插到 7 和 9 之间 → 1 2 3 4 5 7 8 9 | 6第8趟temp69、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 次总和大约是 12...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 手算演示temp5 到底插在哪还是用 arr {9, 3, 7, 1, 5, 4, 2, 8, 6}。前几轮的结果和直接插入排序完全一样到第4轮时已排序部分是 1 3 7 9待插入 temp5。这时二分查找过程是low0, high3, mid1arr[1]3 5所以 low2 low2, high3, mid2arr[2]7 5所以 high1现在 low2, high1low high循环结束插入位置就是 low2。然后把 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。比如 n9 时gap 依次取 4、2、1。这个策略写起来简单理解起来直观是教学和笔试的首选。还有若干更复杂的增量序列可以把最坏复杂度进一步压低。比如取形如 2^k - 1 的增量最坏可以达到 O(n^(3/2)) 左右再进化一些的增量组合甚至可以压到 O(n^(4/3)) 量级。但工程上老老实实用 gap n/2 往下折半的情况非常多因为实现简单、常数小面对绝大多数实际数据已经足够快。面试时能说出“增量序列会影响希尔排序的复杂度”这一点已经比很多人强了。4.3 全过程手算gap4 → 2 → 1还是用那一组数据演示。arr {9, 3, 7, 1, 5, 4, 2, 8, 6}n9。先看 gap4。数组被分成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。注意大的数字已经明显往右边靠了但还未完全有序。接下来 gap2分成两组组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。最后 gap1直接对整个数组做依次插入排序过程其实就是前面的直接插入排序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; } } }很多初学者不理解为什么内层循环不是“先按组分好再一组一组排”而是从 igap 往后一个个处理。其实这两种写法是等价的当 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)。取 gap2。分组为组15a、5c插入排序后保持不变组25b、1插入排序后变成 1、5b。第一趟结束数组变成5a、1、5c、5b。到这里已经能看出问题5b 被移动到了整个数组的末尾。接着 gap1 做直接插入排序1 被插到最前面5c、5b 依次与前面的 5a 比较但都不小于 5a所以位置不再变化。最终顺序为5a、5c、5b、1。原来的顺序是 5a、5b、5c现在 5b 和 5c 的相对位置颠倒了所以希尔排序不稳定。深一层想直接插入排序每个子序列内部是稳定的但不同子序列的元素会在后续增量排序中跨越移动跨越之后没有任何机制能保证相等元素的原有相对次序于是整体稳定性就被破坏了。这也是为什么很多需要稳定排序的业务场景不敢轻易用希尔排序。5. 三种插入排序横向对比与工程选型5.1 一张表看穿复杂度、稳定性和场景为了便于记忆我把三种插入排序放在一张表里排序最好最坏平均空间稳定性直接插入O(n)O(n²)O(n²)O(1)稳定折半插入O(n log n)O(n²)O(n²)O(1)稳定希尔排序取决于增量最坏约 O(n²)常规增量约 O(n^1.3)~O(n²)O(1)不稳定这张表有两点要特别提醒。第一折半插入那一行的“O(n log n)”指的是最好情况别拿去答“平均复杂度”面试官问平均复杂度时标准答案依然是 O(n²)。第二希尔排序的平均复杂度在业界和学术界没有一个非常统一的固定值它和增量序列强相关常规折半增量下实测基本是介于 O(n^1.3) 和 O(n²) 之间回答时强调“依赖增量选择”比硬背一个数字更准确。5.2 面试高频考点与常见误区面试里关于这三种排序的问题翻来覆去就那么几个手写直接插入排序并说明稳定性。折半插入排序比直接插入排序优化了什么复杂度为什么仍然是 O(n²)希尔排序为什么不稳定增量序列有什么影响三种排序分别适合什么场景与之相伴的还有几个非常经典的误区。第一个误区是“折半插入是 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 更稳。另外只要涉及排序稳定性我写比较条件时都会刻意写成“严格大于才交换”这样潜意识里就避免了把稳定排序写崩。三种插入排序看起来只是三个小算法但它们背后的优化链条很值得反复琢磨先能用再少比较再少搬移。把这层逻辑吃透后面学快速排序的基准选择、归并排序的分治合并都会感觉顺很多。最后再分享一个我带过的学生们普遍反馈有效的方法学这块内容先别急着打开编辑器拿一副扑克牌按这三种策略各手动插一遍。直接插入就是一张张往手里插折半插入就是在手牌里猜中间位置然后决定插左边还是右边希尔排序就是先把牌隔几张分成几叠每叠理好再逐步缩小间隔。亲手走过几遍之后再看代码里的循环条件会顺很多。这个习惯我到现在都还在用也希望你能试试。