很多人第一次接触排序算法不是从课本上的伪代码开始的而是在牌桌上。摸一张牌从右往左比过去找到合适的位置插进去顺手把后面的大牌往后挪一格——这个动作重复二十次手里的牌就整整齐齐。后来学数据结构我才知道这个动作有个正式名字叫插入排序。插入排序是排序算法里最贴合人类直觉的一个也是我在实际项目中用得最频繁的排序之一。它思想简单代码也短但真要把它讲透能挖出不少东西为什么稳定、为什么对近似有序的数组特别快、折半插入排序到底优化了什么、以及它为什么至今还活在 TimSort、JDK 排序这类高级算法内部。这篇文章就从这几个角度把插入排序从头到尾拆一遍。文章适合这几类读者刚学算法想弄懂基础排序的初学者准备面试想答好插入排序相关追问的人以及在嵌入式或性能敏感场景里纠结到底用哪个排序的工程师。我会结合代码、手算过程和工程实践来讲保证每个结论都有依据不搞玄学。1. 核心思想把人玩牌的动作翻译成代码1.1 一张牌一张牌地理牌想象你在斗地主左手已经握着一把按从小到大排好的牌右手从桌上拿起一张新牌。接下来你干什么从右往左看手里的牌遇到比新牌大的就往右挪一个位置直到遇到一张比新牌小的或者已经看到最左边然后把新牌放到那个空出来的位置。整个过程里左手始终是一把有序的牌右手每次只处理一张新的。这种一边维护有序序列一边把新元素插进去的思路就是插入排序的全部核心。翻译成数组语言从左到右扫描数组假设当前位置左边的子数组已经有序把当前元素插入到左边子数组的正确位置使左边的子数组仍然有序。这个思路决定了插入排序的两个重要特性它是在线的——你可以在数据源源不断到来时逐个插入并保持整体有序它也是稳定的——两个相等的元素不会因为排序而交换相对位置原因后面细说。1.2 数组视角下的三个动作把上面的过程拆成数组操作其实只有三个动作取出当前待处理的元素暂存到一个变量里比如叫key。比较并右移从当前元素的前一个位置开始依次往左比较凡是比key大的元素统一往右挪一位。插入当遇到第一个不比key大的元素或者已经扫到数组起点就把key放到当前空出的位置。用生活类比来说这就像在一条已经排好队的人群里插入一个新成员。你从队尾往队头走每经过一个比你高的人就请他往后退一步直到前面是个比你矮的人你站到他身后。队伍始终有序新成员也找到了正确位置。1.3 手算一轮完整的插入过程光说概念不过瘾我们用一个具体的例子走一遍。假设数组是[5, 2, 4, 6, 1, 3]初始状态第一个元素5视作已经有序的左子数组。处理22比5小5右移一位2放到开头。数组变为[2, 5, 4, 6, 1, 3]。处理4和5比5右移和2比2不比4大停下。4放到原来5的位置。数组变为[2, 4, 5, 6, 1, 3]。处理6和5比5不比6大直接停在原地。数组不变。处理1一路比过去6、5、4、2全部右移一位1放到开头。数组变为[1, 2, 4, 5, 6, 3]。处理36、5、4右移3放到2后面。数组变为[1, 2, 3, 4, 5, 6]。特别注意处理4那一步当key 4和左边的2比较时因为2 4所以停止移动。这个遇到等于或者小于就停的细节正是插入排序稳定性的来源。如果用作为移动条件相等元素的相对位置就会被破坏稳定性就丢了。这一点后面单独开一节讲。1.4 为什么说它是在线的在线这个词听起来玄乎其实就是说你不需要提前拿到全部数据。数据来一个插一个整个过程结束后所有数据有序。这个特性在几个真实场景里特别值钱。比如你在服务器上维护一个排行榜用户积分不断变化每次只需要把新分数插入到一个有序数组里又比如你在处理实时日志流想随时输出当前已经收到的日志中耗时最长的前若干条。这些场景天然适合插入排序因为它不需要预知未来。相比之下快速排序和归并排序通常需要先拿到完整数据才能开始工作。这也是为什么插入排序虽然平均时间复杂度是 O(n²)但在很多在线场景里依然无法被替代。2. 手写实现移位和交换只差一个赋值2.1 最常见的两版代码直接给出一份最标准的 Python 实现def insertion_sort(arr): for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: arr[j 1] arr[j] j - 1 arr[j 1] key return arrC 语言版本几乎一模一样void insertion_sort(int a[], int n) { for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }两版代码的逻辑完全一致外层循环控制当前插入哪个元素内层循环负责把比它大的元素往右挪。2.2 几个容易被问倒的细节第一为什么不写成交换很多新手会写成这样内层循环里判断arr[j] arr[j1]就交换两个元素。这样写也能排序但没有必要。交换一次需要三次赋值而移位只需要一次赋值。插入排序的内层循环本质是把一系列元素都右移一格最后只写一次key所以用移位而不是交换常数更小。遇到数组元素是结构体或者对象时这个差异会被放大。第二为什么先从i-1开始向左扫描因为我们要找的是第一个不大于key的位置而i-1是当前元素的前一个位置从它开始向左比较天然是从有序子数组的末尾往前扫。这利用了有序子数组的局部性越靠右的元素越接近key真正的位置多数情况下不需要扫完整个左子数组。第三arr[j] key和arr[j] key有什么区别区别就在稳定性上。用时遇到相等的元素就停下把key放到相等元素后面所以相等元素的相对顺序不变用时相等的元素会被移动到key的右边顺序就反了。绝大多数排序需求要求稳定排序标准写法都用。2.3 哨兵优化真的有用吗老教材里经常出现一种哨兵优化在数组最前面留一个空位每次插入前先把这个空位填上key然后内层循环就不需要判断j 0了。// a[0] 做哨兵实际数据从 a[1] 开始n 为数据个数 void insertion_sort_with_sentinel(int a[], int n) { for (int i 2; i n; i) { int key a[i]; int j i - 1; a[0] key; while (a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }原理是当j一直减到0时a[0]已经被设成了key此时a[0] key为假循环自然退出不需要再单独判断j是否为负。内层循环的判断条件从两个j 0 a[j] key减到一个a[j] key每条指令都能省。但我的实际体会是这个优化在现代 CPU 上收益极其有限甚至可以说几乎感觉不到。原因有二。第一现代 CPU 的分支预测器对j 0这种高度规律的模式预测准确率非常高这个判断基本不消耗额外时间第二哨兵版本牺牲了数组的a[0]位置调用方必须把数据从下标 1 开始存对工程代码来说很不友好容易引入差一错误。所以我对哨兵优化的评价是理解它的思路有价值——它在教你减少每次循环里的判断次数、用空间换时间这种底层优化思维但实际项目里我不会为了省一个判断而让数组下标从 1 开始。真正值得用哨兵的地方是超大规模数据配合汇编级优化普通业务代码里收益不成正比。2.4 复杂度到底怎么算插入排序的时间复杂度取决于数据的初始有序程度这是它和其他 O(n²) 排序最不一样的地方。最好情况数组已经完全有序。每个元素只需要和它前一个元素比较一次发现不需要移动直接进入下一轮。比较次数是 n-1移动次数是 0时间复杂度是O(n)。最坏情况数组完全逆序比如[n, n-1, ..., 1]。第 i 个元素插入时需要和前面所有 i 个元素比较并移动总比较次数和移动次数都是 12...(n-1) n(n-1)/2约等于n²/2时间复杂度O(n²)。平均情况每个元素大约需要移动一半的位置总移动次数约为n²/4时间复杂度仍然O(n²)。空间复杂度只用了一个临时变量key所以是O(1)原地排序。这个最好情况 O(n)的特性在排序算法里有个专门名词叫适应性。一个算法越能利用数据已有的有序性适应性越强。插入排序的适应性是所有基础排序里最强的这也是它在工程中依然有一席之地的根本原因。3. 折半插入排序省了比较没省移动3.1 它优化了什么很多人学完插入排序后会想内层循环每轮都在做两件事——比较和移动。如果我能更快地找到插入位置不就能让整个排序变快了吗这个思路就是折半插入排序的出发点。既然左子数组已经有序那为什么还要从左往右一个一个比直接在上面做二分查找定位插入位置不是更高效吗理论上确实如此。直接插入排序在插入第 i 个元素时平均要比较 i/2 次折半插入排序通过二分查找把比较次数降到 log₂(i) 次。整个排序下来比较次数从 O(n²) 降到了O(n log n)。def binary_insertion_sort(arr): n len(arr) for i in range(1, n): key arr[i] left, right 0, i while left right: mid (left right) // 2 if arr[mid] key: left mid 1 else: right mid # left 即为 key 应该插入的位置 for j in range(i, left, -1): arr[j] arr[j - 1] arr[left] key return arr注意这里二分查找的边界条件right一开始是i而不是i-1。这能让查找区间覆盖到插入到最右边的情况——也就是key比左子数组所有元素都大的时候left最终会是i位置合法。如果你把right设成i-1边界情况就会出错。3.2 二分定位要小心边界折半插入排序最容易写错的地方不是二分查找本身而是查找相等元素时该往哪边收缩。我的代码里用的是if arr[mid] key: left mid 1这个分支。当arr[mid] key时继续往右半部分找这样最终得到的left指向的是第一个大于key的位置也就是相等元素区间的右边。把key插到这个位置所有和key相等的元素都会留在它前面相对顺序不变稳定性得以保留。如果你把条件写成if arr[mid] key那么left会收敛到第一个大于等于key的位置key会插到相等元素的最前面相等元素的相对顺序就倒过来了。数组元素是整数时无所谓但数组元素是对象、需要按某个字段排序同时又要求其他字段保持原顺序时这个差别会直接导致结果不符合预期。3.3 实测中的收益和大数组陷阱那折半插入排序是不是全面优于直接插入排序不是这里有个非常大的误区。折半插入排序只是把比较次数从 O(n²) 降到了 O(n log n)但移动次数仍然是 O(n²)。因为不管你怎么找到位置插入一个元素时它后面的所有元素照样得往右挪一格。换句话说算法的时间复杂度依然是O(n²)只是常数变小了。举个例子对一个长度为 10000 的逆序数组直接插入排序大约需要比较和移动各 5000 万次折半插入排序比较次数降到约 13 万次但移动次数还是约 5000 万次。总耗时确实少了但少的是比较这部分移动的大头一点没动。所以折半插入排序的真正适用场景是元素比较的开销远大于移动的开销。比如数组里存的是很长的字符串、复杂的结构体一次比较可能要遍历几百上千字节而移动只是一个指针赋值代价极小。这时候把比较次数从 O(n²) 降到 O(n log n) 是实实在在的收益。反过来如果数组元素是整数、浮点数这种比较开销极小的类型折半带来的优化几乎感知不到代码还更复杂我通常就直接用普通插入排序。还有一个容易忽略的实际问题折半插入排序失去了插入排序的强适应性。直接插入排序在数据近乎有序时内层循环往往比较一两次就退出几乎不移动但折半插入排序无论数据是否有序每个元素都要完整走一遍二分查找固定消耗 O(i log i) 的比较次数。有序数组用直接插入是 O(n)用折半插入反而是 O(n log n)完全倒挂了。所以如果你的数据大概率是几乎有序的老老实实用直接插入排序别用折半版本。4. 稳定性与适应性面试官最爱追问的隐藏属性4.1 稳定性的来源是那个号什么叫稳定排序简单说就是如果数组里有两个值相等的元素排序后它们的相对前后顺序不能变。插入排序正是稳定的关键就在代码里的那个号。当key遇到一个等于它的元素时移动循环立刻停止key就被插到那个相等元素的后面。从头到尾两个相等元素的相对顺序没有被破坏。这个特性在很多真实场景里很重要。比如你有一批订单先按下单时间排好序再按金额排序。如果用的是稳定排序相同金额的订单仍然按下单时间顺序排列如果用不稳定排序相同金额的订单顺序就乱了。对比一下选择排序它每次选出最小值放到前面如果某个位置之前正好有一个与之相等的元素交换时就会把相等的元素交换到后面去破坏稳定性。这也是为什么我常说在 O(n²) 级别的基础排序里插入排序的稳定性是白送的不需要额外付出任何代价。4.2 适应性近乎有序数据的杀手锏插入排序对几乎有序的数据处理得极快这是它最容易被低估的优点。想象一个数组只有最后几个元素是乱的前面几万个元素已经有序。快速排序大概会递归若干层每次划分都要做一轮遍历归并排序需要额外的 O(n) 空间但插入排序只需要处理那几个乱序的元素每个乱序元素往左移动一小段距离就结束整体复杂度接近 O(n)。我自己在线上环境处理过类似问题一个配置表每天只有少量条目变化其余几千条保持原顺序。直接用插入排序对全量数据排序每次耗时在毫秒级换成 O(n log n) 的排序算法反而因为常数大、递归栈深耗时更高。这个场景下插入排序的适应性比理论上的时间复杂度重要得多。4.3 和其他 O(n²) 排序的对比把插入排序、选择排序、冒泡排序放在一起看很多特性一目了然算法平均时间最好时间最坏时间稳定性适应性额外空间插入排序O(n²)O(n)O(n²)稳定强O(1)选择排序O(n²)O(n²)O(n²)不稳定无O(1)冒泡排序O(n²)O(n)O(n²)稳定弱O(1)选择排序唯一的优势是交换次数固定为 n-1如果写操作的代价远高于读操作比如 Flash 存储它有存在价值但排序速度上它没有任何优势因为它无论数据是否有序都要完整扫描完整个数组。冒泡排序也有适应性和稳定性但它的实现天生要频繁交换相邻元素每次交换需要三次赋值而插入排序的移位只需要一次赋值。同样处理近似有序的数组插入排序的常数比冒泡小很多。所以我常说这三个 O(n²) 排序里插入排序是综合最优的那个工程上几乎总是优先选它。5. 大规模工程里的插入排序它从未离开5.1 快排的阈值和 TimSort有个反直觉的事实快速排序在数据量很小的时候并不比插入排序快甚至更慢。原因在于快速排序有递归调用、有函数栈、有更复杂的划分逻辑这些开销对几十个元素来说完全是浪费。所以几乎所有工业级的快速排序实现都会在递归到小数组时切换到插入排序。这个切换阈值通常在 8 到 32 之间。比如经典的快速排序优化策略就是当子数组长度小于等于INSERTION_SORT_THRESHOLD时调用插入排序而不是继续递归。另一个更典型的例子是TimSort。Python 的sorted()和 Java 对对象数组的排序用的都是 TimSort。它的核心思路是把数组切成若干个已经有顺序的run对太短的 run 用二分插入排序扩展到最小长度然后再用归并把这些 run 合并起来。换句话说插入排序在这个高级算法里担任了基石的角色。5.2 JDK 里的成对插入排序我印象最深的一个优化来自 JDK 的DualPivotQuicksort。它对小于 47 个元素的数组用的是成对插入排序英文叫 pair insertion sort。这个名字听着高级思路其实很朴素普通插入排序每轮处理一个元素每轮都要维护一次外层循环的计数器 i 和比较逻辑成对插入排序每轮固定处理两个相邻元素先把较大的那个插入到前面有序区再把较小的那个插入到前面。这样做最大的好处是外层循环的次数减半循环控制本身的分支判断也少了一半。示意思路如下// 成对插入排序的核心思想每次处理两个元素 for (int i 1; i n; i 2) { // 取 a[i] 和 a[i1] 两个元素较大的先插入较小的再插入 // 外层循环次数比普通插入排序少一半 }这个优化在数据量小的时候效果显著因为小数组排序的瓶颈往往不在比较次数而在循环控制和分支预测。我第一次看到 JDK 这段源码时挺震撼的原来算法已经最优之后工程上还能从指令级别再扣出性能来。5.3 你天天在用的增量排序除了作为大算法内部的组件插入排序本身在业务代码里也经常直接上场。最典型的是增量维护有序序列。比如游戏服务器里有一个玩家排行榜玩家数量不多几百人。新玩家注册或者老玩家分数更新你需要把新的分数插入到有序列表里。这时候用插入排序的思维就是最自然的解法从列表尾部往前扫描把比新分数低的玩家往后挪一位找到位置插进去。整个过程 O(n)不需要对全表重新排序。再比如实时监控系统里你需要维护当前延迟最高的前 100 个请求。每来一条新请求如果它的延迟能进前 100就把它插入到有序数组的合适位置把第 101 个挤出去。这种数据流式到达随时需要有序结果的场景插入排序几乎是量身定做的。5.4 我的实践建议做了这么多年开发我在不同场景下对排序的选型经验可以总结成几条数组长度小于 16无脑用插入排序别纠结。哪怕数据完全乱序它也是最稳的选择代码量小没有递归栈不容易出错。数据量中等但大概率近乎有序用插入排序。利用它的适应性往往比上来就快排快得多。比较开销远大于移动开销用折半插入排序。典型的例子是字符串数组或者含大结构体的数组。需要稳定排序且不想引入额外内存插入排序是最容易写对的稳定 O(n²) 排序。有一次我在嵌入式设备上处理传感器数据排序芯片主频低内存只有几十 KB不能用递归算法也不能申请额外数组。最后就是直接用插入排序代码不到二十行稳定、原地、常数小跑得稳稳当当。这种场景下高级算法反而帮不上忙反而是最朴素的插入排序最可靠。关于插入排序想说的就这么多。它看似简单但往深了挖有稳定性、适应性、二分优化、哨兵技巧甚至还有像成对插入排序这样的工业级微优化。理解它最好的方式还是自己多写几遍然后故意把数据改成完全逆序看一眼耗时再改成完全有序看一眼耗时那种差距会让你印象非常深刻。下次再有人问插入排序不就是个 O(n²) 的简单算法吗你就可以告诉他简单归简单它每天在 TimSort 里、在 JDK 里、在你眼前的数据库排序里替你干了不知道多少活。