2.3.插入排序——像打牌一样整理数组，为什么它对“几乎有序”数据特别友好？

2.3.插入排序——像打牌一样整理数组为什么它对“几乎有序”数据特别友好系列搜索与排序 | 第 3 篇共 16 篇难度⭐☆☆☆☆ 入门级标签排序插入排序稳定排序基础算法小数据优化上一篇2.2.选择排序——每轮找最小为什么交换更少却反而不稳定下一篇2.4.快速排序——先分区再递归为什么它平均这么快却可能退化前言“插入排序不也是 O(n²) 吗为什么它的口碑往往比冒泡和选择更好”这是很多初学者学到第三个基础排序时都会冒出来的问题。插入排序表面上看也不复杂每次拿一个新元素插到前面已经有序的部分里。但真正往下挖你会发现它有几个很值得讲透的点为什么它像“整理手里的扑克牌”为什么它在最坏情况下还是 O(n²)却对“几乎有序”数据特别友好为什么它是稳定排序为什么很多工程实现会在小区间切换到插入排序它和希尔排序、链表排序之间又有什么联系这篇就把插入排序讲透。一、算法思想维护前缀有序区间插入排序的核心思想很直观把数组看成“前面已经有序、后面还未处理”两部分每一轮从后半部分拿出一个元素把它插入到前半部分的正确位置。假设数组长度为n初始时可以认为第0个元素自己就是一个长度为 1 的有序区间第 1 轮把第1个元素插入到区间[0, 0]中第 2 轮把第2个元素插入到区间[0, 1]中第 3 轮把第3个元素插入到区间[0, 2]中……第n-1轮结束后整个数组有序核心不变量第i轮结束后区间[0, i]已经有序并且保持了这i1个元素在排序后的正确相对顺序。这也是它和前两篇算法的区别冒泡排序不断交换相邻元素把大元素往后“推”选择排序扫描未排序区间把最值“选”出来插入排序把当前元素拿出来插入到前面有序区间的合适位置如果你打过扑克牌这个过程会非常自然手牌左边已经排好序右手新摸到一张牌从右往左找位置给它腾出空位再把它插进去这就是插入排序。二、完整图解过程以数组[5, 3, 8, 1, 2]为例逐步演示插入排序的全过程。第 1 轮把3插入到[5]中初始 [5 | 3, 8, 1, 2] ↑ 左边视为已排序区间 取出 key 3 比较 5 和 35 35 右移一位 腾出位置后把 3 放进去 结果 [3, 5 | 8, 1, 2]第 2 轮把8插入到[3, 5]中当前 [3, 5 | 8, 1, 2] 取出 key 8 比较 5 和 85 8不需要移动 直接放在末尾 结果 [3, 5, 8 | 1, 2]这一步很能体现插入排序的特点如果当前元素本来就比前面的都大那它几乎不用动这也是它在“几乎有序”数据上会很快的原因之一第 3 轮把1插入到[3, 5, 8]中当前 [3, 5, 8 | 1, 2] 取出 key 1 比较 8 和 18 18 右移 比较 5 和 15 15 右移 比较 3 和 13 13 右移 腾出第 0 位后把 1 放进去 结果 [1, 3, 5, 8 | 2]这一轮能看出插入排序的本质它不是不断交换而是先把key暂存起来再把比它大的元素整体向右挪最后一次性落位第 4 轮把2插入到[1, 3, 5, 8]中当前 [1, 3, 5, 8 | 2] 取出 key 2 比较 8 和 28 28 右移 比较 5 和 25 25 右移 比较 3 和 23 23 右移 比较 1 和 21 2停止 把 2 放到 1 后面 结果 [1, 2, 3, 5, 8]最终结果[1, 2, 3, 5, 8]✅整体过程汇总轮次当前 key已排序区间变化结果第 1 轮3[5] - [3, 5][3, 5, 8, 1, 2]第 2 轮8[3, 5] - [3, 5, 8][3, 5, 8, 1, 2]第 3 轮1[3, 5, 8] - [1, 3, 5, 8][1, 3, 5, 8, 2]第 4 轮2[1, 3, 5, 8] - [1, 2, 3, 5, 8][1, 2, 3, 5, 8]三、代码实现Python 版本带注释definsertion_sort(arr):nlen(arr)foriinrange(1,n):keyarr[i]# 当前待插入元素ji-1# 把所有比 key 大的元素向右移动一位whilej0andarr[j]key:arr[j1]arr[j]j-1# 把 key 放到正确位置arr[j1]keyreturnarr arr[5,3,8,1,2]print(insertion_sort(arr))# [1, 2, 3, 5, 8]C 版本#includeiostream#includevectorusingnamespacestd;voidinsertionSort(vectorintarr){intnarr.size();for(inti1;in;i){intkeyarr[i];intji-1;while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;}}intmain(){vectorintarr{5,3,8,1,2};insertionSort(arr);for(intx:arr){coutx ;}return0;}四、复杂度分析1时间复杂度情况时间复杂度原因最好情况O(n)数组本身有序每轮只需比较一次几乎不用移动最坏情况O(n²)数组完全逆序第i轮可能要移动i个元素平均情况O(n²)平均每轮都要向左寻找插入位置最好情况为什么是O(n)因为如果数组已经有序比如[1, 2, 3, 4, 5]那么每一轮都会发生key取出来与前一个元素比较一次发现不用动直接结束总共只需要做大约n-1次比较所以是O(n)。最坏情况为什么是O(n²)因为如果数组完全逆序比如[5, 4, 3, 2, 1]那么第 1 轮移动 1 次第 2 轮移动 2 次第 3 轮移动 3 次……第n-1轮移动n-1次总操作量约为1 2 3 ... (n-1) n(n-1)/2 O(n²)2空间复杂度指标值原因空间复杂度O(1)只使用了key、j等少量辅助变量是否原地✅不需要额外数组3数据移动特点插入排序最值得记住的一点是它的比较和移动次数不是固定的而是跟数组“离有序还有多远”强相关。这也是它和选择排序最不一样的地方选择排序的比较次数几乎固定插入排序的工作量会随着“逆序程度”变化五、稳定性为什么它是稳定排序先回顾稳定性的定义如果两个相等元素在排序前后的相对顺序不变那么这个排序算法就是稳定的。插入排序是稳定排序。原因就在这句条件判断while(j0arr[j]key)注意这里写的是arr[j] key而不是arr[j] key这意味着只有当前面的元素严格大于key时才会右移如果前面的元素和key相等就不会继续右移于是后出现的相等元素只会被插到前面相等元素的后面六、为什么它对“几乎有序”数据特别友好这是插入排序最有价值的一个性质。如果数组本来就差不多有序那么每一轮插入时key往左移动的距离很短甚至很多轮根本不用移动因而总开销会非常小比如数组[1, 2, 3, 4, 6, 5, 7, 8]这里只有6和5的位置有点不对。插入排序处理到5时把6右移一位再把5放到6前面整个数组就已经有序了。也就是说它没有做很多“无意义的大动作”。一个更本质的理解它和逆序对数量有关设数组中的逆序对数量为k。对于插入排序来说内层while循环每执行一次本质上都在消除一个“当前 key 与前面某个元素”的逆序关系因此可以把插入排序的时间复杂度理解成O(n k)其中n是外层扫描一遍数组的成本k是需要通过移动元素来消除的逆序关系数量这就解释了为什么数据越接近有序插入排序越快在某些近乎有序的小数组里它甚至会比快排、归并这类O(n log n)算法更顺手这也是很多工程实现会在小区间或近乎有序区间里切换到插入排序的原因。七、优化与变体优化 1使用“后移”而不是频繁交换很多初学者第一次写插入排序时会把它写成这样遇到逆序就不断swap交换相邻元素虽然逻辑上也能排出来但这样会产生更多赋值操作。更推荐的标准写法是先把当前元素保存到key把所有比key大的元素统一右移最后一次性把key放到空出来的位置也就是我们前面代码里的这种写法。它的好处是代码逻辑更清楚数据写入次数更少更符合插入排序“腾位置再落位”的本质变体 2二分插入排序插入排序有两个主要成本比较找插入位置移动给key腾位置如果想减少比较次数可以在已经有序的区间里用二分查找定位插入位置。#includevectorusingnamespacestd;voidbinaryInsertionSort(vectorintarr){intnarr.size();for(inti1;in;i){intkeyarr[i];intleft0,righti-1;while(leftright){intmidleft(right-left)/2;if(arr[mid]key){rightmid-1;}else{leftmid1;}}for(intji-1;jleft;j--){arr[j1]arr[j];}arr[left]key;}}它的特点是查找插入位置从线性扫描变成二分查找比较次数减少了但元素右移的次数并没有本质减少所以二分插入排序不能把整体复杂度降到 O(n log n)因为移动元素的成本仍然可能是 O(n²)。变体 3希尔排序本质上是“分组插入”如果继续沿着“插入排序太怕远距离逆序”这个问题往前走就会得到一个更强的改进思路先让相距较远的元素也能提前比较和移动再逐步缩小间隔最后回到普通插入排序收尾这就是希尔排序的核心想法。后续讲到希尔排序时再详细说。八、与冒泡排序、选择排序对比对比项冒泡排序选择排序插入排序核心动作相邻比较并交换扫描后选最值交换取出当前元素插入前面有序区间最好时间复杂度O(n)O(n²)O(n)平均时间复杂度O(n²)O(n²)O(n²)稳定性稳定不稳定稳定对几乎有序数据是否友好较友好不友好非常友好数据移动特点交换频繁交换少但比较固定以“元素后移 最后落位”为主工程小数组优化价值一般一般较高一句话总结冒泡是在“推”选择是在“挑”插入是在“腾位置后放进去”。九、OJ 例题讲解例题 1LeetCode 1051 — 高度检查器小数据插入排序可直接通过题目来源LeetCode题号 1051难度⭐☆☆☆☆ 简单题目链接https://leetcode.cn/problems/height-checker/题目描述给你一个整数数组heights表示学生当前站位的身高。把它按非递减顺序排好后统计有多少个位置上的值与原数组不同。数据范围1 n 1001 heights[i] 100为什么这题适合用插入排序这题的数据规模非常小n最多只有100。所以完全可以先复制原数组对副本使用插入排序再逐位比较原数组与排序后数组统计不同位置数量也就是说这不是“只能拿来做模板练习”的题而是一道直接手写插入排序也能顺利通过的基础题。C 解法插入排序写法// 头文件编译平台提供classSolution{public:intheightChecker(vectorintheights){vectorintexpectedheights;intnexpected.size();for(inti1;in;i){intkeyexpected[i];intji-1;while(j0expected[j]key){expected[j1]expected[j];j--;}expected[j1]key;}intans0;for(inti0;in;i){if(heights[i]!expected[i]){ans;}}returnans;}};这题适合拿来练什么练最标准的数组插入排序模板练“排序后再比较”的常见解题套路体会小数据范围下O(n²)算法依然完全可用例题 2LeetCode 147 — 对链表进行插入排序思想直接对应题目来源LeetCode题号 147难度⭐⭐⭐☆☆ 中等题目链接https://leetcode.cn/problems/insertion-sort-list/题目描述给定单链表的头节点head请你使用插入排序对链表进行排序并返回排序后的链表头节点。Definition for singly-linked list.struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}};为什么这题和插入排序高度匹配因为题目要求的就是“链表版插入排序”。它和数组版插入排序的共同点是都维护一个“已经有序”的部分每次从未排序部分取出一个元素把它插到已排序部分的正确位置不同点在于数组插入时往往要移动一串元素链表插入时不需要搬值只要改指针所以这题非常适合帮助你理解插入排序的核心不在“数组”而在“把一个新元素插到已有序结构中”。C 解法/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public:ListNode*insertionSortList(ListNode*head){ListNodedummy(0);// 无实际意义的头结点用dummy-next来指当前生成的链表ListNode*curhead;while(cur!nullptr){ListNode*nextNodecur-next;ListNode*prevdummy;while(prev-next!nullptrprev-next-valcur-val){prevprev-next;}cur-nextprev-next;prev-nextcur;curnextNode;}returndummy.next;}};这题适合拿来练什么练“插入排序思想”和“链表操作”结合练虚拟头结点dummy的写法理解为什么链表在“插入”这件事上天然比数组更顺手例题 3POJ 1007 — DNA Sorting稳定排序的价值题目来源POJ / PKU OJ题号 1007难度⭐⭐☆☆☆题目链接http://poj.org/problem?id1007题目描述给你m个长度为n的 DNA 字符串需要按每个字符串的“逆序数”从小到大进行稳定排序后输出。数据范围n 50m 100为什么这题适合出现在插入排序章节这题和插入排序的契合点非常强数据量不大m最多只有100完全可以直接手写稳定排序题目明确要求稳定排序而插入排序天然稳定排序对象不是整数而是“带权记录”更能体现稳定排序在真实题目里的价值也就是说这题不是单纯的“把数字排一下”而是要你意识到当排序键相同、又要求保留原顺序时稳定排序就很重要。C 解法计算逆序数 稳定插入排序#includeiostream#includestring#includevectorusingnamespacestd;structNode{string s;intscore;};intgetScore(conststrings){intcnt0;intns.size();for(inti0;in;i){for(intji1;jn;j){if(s[i]s[j]){cnt;}}}returncnt;}intmain(){intn,m;cinnm;vectorNodearr(m);for(inti0;im;i){cinarr[i].s;arr[i].scoregetScore(arr[i].s);}for(inti1;im;i){Node keyarr[i];intji-1;while(j0arr[j].scorekey.score){arr[j1]arr[j];j--;}arr[j1]key;}for(inti0;im;i){coutarr[i].sendl;}return0;}这题适合拿来练什么练“结构体排序”而不是“纯整数排序”练稳定排序的真实使用场景体会插入排序为什么在小规模、稳定性要求明确的题里依然有价值十、适用场景场景是否适用原因数据量很小如n 50或n 100✅常数小、代码短、实现简单数组几乎有序✅总移动距离短速度很可观需要稳定排序✅相等元素相对顺序不变小区间工程优化✅常作为大排序算法的小区间收尾方案大规模随机数组❌平均仍是 O(n²)不适合主力排序元素远距离错位很多❌会产生大量后移操作十一、常见错误总结错误原因正确做法每次比较都直接交换相邻元素把“后移插入”写成了“频繁交换”先保存key统一后移赋值再一次落位while写成arr[j] key会破坏稳定性只在arr[j] key时右移忘记最后arr[j 1] key找到了位置却没真正插进去循环结束后必须落位误以为二分插入排序是 O(n log n)忽略了元素移动成本比较次数降了但移动仍可能是 O(n²)误以为它只适合教学忽略了它对近乎有序数据和小区间优化的价值记住它在工程里也常被拿来做小范围收尾总结要点内容核心思想每轮取出一个元素插入到前面已经有序的区间中时间复杂度最好 O(n)平均/最坏 O(n²)空间复杂度O(1)原地排序稳定性✅ 稳定关键特点对几乎有序数据特别友好思想延伸二分插入、链表插入、希尔排序一句话记住它插入排序最像人手整理扑克手牌——每接收一个新排新元素把它插入手牌中对应位置插入已有序队列中的对应位置上一篇2.2.选择排序——每轮找最小为什么交换更少却反而不稳定下一篇2.4.快速排序——先分区再递归为什么它平均这么快却可能退化看完有收获的话点个赞再走有问题欢迎评论区讨论