第一次学插入排序的时候我脑子里只有一个画面深夜里打牌手里一摞牌已经按大小排好了摸到一张新牌先从左到右或者从右到左扫一眼找到位置把牌往里一塞后面的牌顺手往后挪一挪。后来才知道这个动作在算法里有个精确的名字——插入排序而且它远不只是“一种”排序那么简单。插入排序的核心思想一句话就能说清维护一个已经有序的前缀每次把当前元素插到前缀里合适的位置。听起来很简单但真正把它写成Python代码时很多人却会在边界条件、元素覆盖、稳定性这些地方卡住。这篇笔记不打算堆概念我尽量用“理扑克牌”的视角把整个过程掰开揉碎从直觉、代码、复杂度、优化到手写时容易踩的坑一次性说透。适合刚学排序算法的同学也适合准备面试但想快速温习细节的人。如果你已经把插入排序背得滚瓜烂熟可以重点看第4章和第5章那里有一些文档里不会写的东西。1. 插入排序到底在排什么先建立直觉1.1 从一局牌桌说起想象你左手拿着一把已经从小到大排好的扑克牌右手摸到了新牌。你不会把整手牌全部打散重新排而是从最右边那张最大的牌开始一张一张往左比较新牌比当前这张小就把当前这张往右挪一位继续比较直到遇到一张比新牌小的牌或者已经走到最左边然后把手里的新牌插到那个空出来的位置。这里有几个关键动作比较、后移、插入。对应到数组上数组的左边部分就是我们左手里“已经排好序”的牌数组右边部分还是没摸上来的乱牌。每一步把乱牌里的第一个元素当作“新牌”然后“插入”到左侧有序区的合适位置。因为左侧始终是有序的所以插入之后左侧的有序区就变长了一个元素。这个直觉看起来简单但许多人写代码时会把“找位置”和“移动元素”分成两步先用循环找到插入点再把后面的元素整体右移最后放入新值。这样当然也能实现但代码容易写碎。标准插入排序的做法是把比较和移动合并成一个循环从右往左找位置的过程中顺手把比新牌大的元素往右挪这样循环结束时空位自然就是新牌该待的地方。1.2 插入、选择、冒泡三个容易混淆的排序初学排序时最容易把插入排序、选择排序、冒泡排序搅在一起。它们都是O(n²)级别的基础排序但思路完全不同。插入排序维护左侧有序前缀每次把“当前牌”插入到有序前缀的合适位置。它强调的是“插入”这个动作后面的元素整体后移。选择排序每次从右侧未排序区里选出最小或最大的元素和未排序区的第一个元素交换从而扩大左侧有序区。它强调的是“选择”和已经有序的部分没有关系每次扫描都要做完整比较。冒泡排序通过反复交换相邻的逆序对让大的元素像气泡一样慢慢浮到数组末尾。它强调的是“交换”每一轮结束至少有一个元素到达最终位置。从“局部有序性”来看插入排序很特殊它在整个排序过程中的每一步左侧都是一个完整的有序序列。而选择排序和冒泡排序在中间阶段只有“部分位置正确”整体并不收敛成一个不断扩大的有序区。正因为这个特点插入排序对“几乎有序”的数据特别敏感如果输入已经接近有序需要移动的元素很少它跑得非常快而选择排序不管输入多有序比较次数都是一样的。1.3 不要被“排序”限制思路插入排序本质上是一种在线算法数据一个一个到达也能随时维持整体有序。比如你正在做实时排行榜新分数不断进来需要在列表里插入一条新纪录并保持有序又比如财务系统按时间追加交易记录同时要求账目始终按金额排列。这时候你不需要每次都调用完整排序只要对新元素执行一次“插入”动作就行。这个“在线”视角还能帮你理解为什么很多工业级排序会把插入排序当作基座。复杂排序通常用分治思想把大问题切成小问题但当问题切到很小的时候递归、分区这些复杂操作的开销反而比插入排序的简单循环更大。于是很多混合排序算法会在子数组足够小时切回插入排序。后面第5.2节我会再展开聊这个问题。2. Python代码实现与每一步拆解2.1 最直观的移位法下面这段代码是插入排序的标准写法也是我在面试和项目里最常使用的版本def insertion_sort(arr): 原地插入排序直接修改传入列表返回同一个列表 n len(arr) for i in range(1, n): # i 是新牌在数组中的下标 key arr[i] # 先把新牌抽出来临时保存 j i - 1 # j 从左侧有序区的最后一个元素开始 while j 0 and arr[j] key: arr[j 1] arr[j] # 比新牌大的元素整体右移一位 j - 1 arr[j 1] key # 把新牌放进空出来的位置 return arr我来逐行解释这里面的思路。for i in range(1, n)为什么要从1开始因为arr[0]单独一个元素天然就是有序的。我们只需要处理从第二个元素开始的所有“新牌”。key arr[i]抽取新牌。这步不能省后面移动元素时会覆盖arr[i]的位置如果不先把值保存下来原来的数据就丢了。j i - 1指向有序区的最后一个元素也就是新牌左边的第一个位置。while j 0 and arr[j] key从右往左扫描。只要当前位置的元素比新牌大就说明新牌应该插在它前面所以把这个元素右移一格。arr[j 1] key循环结束时j已经停在“第一个不大于新牌的元素”的位置或者j -1说明新牌应该放在整个有序区的最前面。无论哪种情况j 1都是新牌的正确插入点。注意这个版本是从小到大排序。如果想从大到小只要把比较条件改成arr[j] key即可。2.2 肉眼模拟一次排序过程文字解释再多也不如直接跑一遍过程。以[5, 2, 4, 6, 1, 3]为例我把它每一轮的状态整理成下表。第几轮 i新牌 key有序区变化过程本轮结束后数组i125 25右移一位2插入到最前面[2, 5, 4, 6, 1, 3]i245 45右移2 4停止4插入到2和5之间[2, 4, 5, 6, 1, 3]i365 6停止6本来就该在最后不需要移动[2, 4, 5, 6, 1, 3]i4161右移51右移41右移21右移1插入到最前面[1, 2, 4, 5, 6, 3]i5363右移53右移43右移23停止3插入到2和4之间[1, 2, 3, 4, 5, 6]观察i3这一轮会特别有意思新牌6已经是当前有序区[2,4,5]里最大的所以while条件一次都不满足直接原地放着。这正是插入排序在最好情况下的状态如果整个数组一开始就是升序每一轮只做一次比较不做任何移动时间复杂度是O(n)。2.3 为什么从后往前扫描为什么必须暂存key很多初学者会问从前往后找插入位置不也一样吗理论上当然可以但标准插入排序坚持从后往前扫有两个原因。第一从后往前扫描可以把“找位置”和“后移元素”合并成一次遍历。我们从有序区末尾开始比较遇到一个比新牌大的元素就让它右移一位然后继续比较前一个。这样当循环停止时所有比新牌大的元素都已经移动过了空位正好是新牌要放的位置。如果从前往后扫你得先花一轮找到插入点再单独把插入点之后的元素整体后移多一次循环代码也更啰嗦。第二从后往前扫描可以避免复杂的元素覆盖顺序问题。想象从前往后移动元素你必须小心翼翼地从插入点开始把后面每个元素依次往后移期间新牌原位置可能先被覆盖导致数据丢失。而标准写法先抽出key所以即使arr[i]的位置被覆盖也完全没影响。key的存在是这个算法正确性的核心。有些人为了省一行变量直接写成while j 0 and arr[j] arr[i]看起来好像没问题但实际上随着循环中arr[j1] arr[j]不断执行arr[i]的值可能已经被改掉了后面再比较就不是原来的“新牌”。我在第4.1节还会专门讲这个坑。2.4 另一种教学写法交换式版本如果你刚开始接触插入排序可能会看到下面这种写法def insertion_sort_swap(arr): for i in range(1, len(arr)): j i while j 0 and arr[j] arr[j - 1]: arr[j], arr[j - 1] arr[j - 1], arr[j] j - 1 return arr这版更像“新牌不断和左边的牌交换位置直到停下来”。它非常好懂每一轮就是把一个元素向左“冒泡”到有序区。但问题是Python的a, b b, a交换在底层也会产生多次赋值操作实际上比移位法多不少常数开销而且每次交换都会改变数组里的两个位置逻辑上不够简洁。我建议初学阶段可以用交换式版本理解过程真正需要写高效或面试手写时用第一节的移位法。移位法才是工业代码里常见的形态。3. 复杂度、稳定性与优化空间3.1 时间复杂度最好、最坏、平均怎么算时间复杂度是对算法规模增长趋势的描述插入排序的复杂度分析能帮助我们理解它为什么适合某些场景。最好情况输入数组已经是升序。每一轮while条件第一次就不满足只做一次比较总共执行n-1次比较移动次数为0。时间复杂度为O(n)。最坏情况输入数组完全逆序。每一轮新牌都要和有序区里所有元素比较并且全部右移。第i轮最多移动i次总移动次数就是1 2 ... (n-1) n(n-1)/2所以是O(n²)。平均情况对一个随机排列的数组新牌平均要移动大约一半的元素所以总移动次数约为n²/4仍然是O(n²)。这里有个更本质的概念叫逆序数数组中逆序对前面的元素大于后面的元素的数量。插入排序每一轮移动的次数恰好等于这个新牌和它左侧元素形成的逆序对数量。整个排序过程的总移动次数就等于数组的逆序对总数。这也是为什么“几乎有序”的数组能让插入排序跑得飞快——因为逆序数本身就很少。3.2 空间复杂度和稳定性空间复杂度很好理解只在原数组上操作额外只有key、j等几个常数级变量所以是O(1)属于原地排序。稳定性就比较有意思了。判断标准是如果两个相等的元素在原始数组中的相对顺序排序后是否保持不变。插入排序的循环条件是arr[j] key注意是严格大于不包括等于。也就是说当遇到和key相等的元素时循环会停止新牌会被插到这个相等元素的右边。因此相同元素的先后顺序不会改变插入排序是稳定排序。稳定性在实际开发里非常重要。比如你有一个员工列表先按部门排好了序现在希望在同一部门内再按入职日期排序。如果排序算法不稳定按入职日期排完原来按部门排好的顺序可能就乱了。但稳定排序可以做到先按部门排序再按日期排序结果就是部门有序、部门内部日期也有序。这道经典场景值得在面试时主动提一下能加分。3.3 二分插入排序看起来优化了但没完全优化既然插入排序的时间都花在“寻找插入位置”和“移动元素”上那能不能用二分查找快速找到位置减少比较次数当然能这就是二分插入排序。import bisect def insertion_sort_bisect(arr): for i in range(1, len(arr)): key arr[i] # 在 arr[0:i] 中查找 key 的插入位置保持稳定性 pos bisect.bisect_right(arr, key, 0, i) # 将 pos 到 i-1 的元素整体右移一位 for j in range(i, pos, -1): arr[j] arr[j - 1] arr[pos] key return arrbisect.bisect_right会返回第一个大于key的位置这样相等元素会插到已有相等元素右侧保持稳定性。这段代码把查找插入位置的时间从O(i)降到了O(log i)总比较次数变成O(n log n)。但移动元素的次数一点都没变依然是O(n²)。所以二分插入排序的整体时间复杂度仍然是O(n²)只是常数变小了。它真正的价值在于“比较代价昂贵的场景”。如果你的数组元素是复杂对象每次比较都需要从磁盘读取或者解密计算降低比较次数就很有意义。但如果是简单的数字排序二分查找带来的额外代码复杂度可能并不划算。3.4 希尔排序是插入排序的嫡系后代讲插入排序时我不能不提希尔排序。因为希尔排序的思路很简单先把数组按间隔gap分成若干组对每组做插入排序然后缩小gap再重复直到gap1做最后一次普通插入排序。它利用了插入排序在“基本有序”时效率极高的特性让元素能快速跨越长距离移动。代码上希尔排序几乎就是把插入排序里的1替换成gapdef shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key gap // 2 return arr希尔排序是第一个突破O(n²)的排序算法虽然不同增量序列下的时间复杂度分析比较复杂但至少告诉我们插入排序的“插入”思想并不是一个死胡同它延伸出了不少工程上实用的变体。4. 手写练习常见错误与调试技巧4.1 三个新手必踩的坑我在教学和面试手写中见过太多人栽在这三个地方这里逐个拆开讲。坑一while条件顺序写反。# 错误示例 while arr[j] key and j 0: # 先访问 arr[j]再判断 j0 ...当j已经减到-1时arr[-1]在Python里并不会报下标越界但会访问到列表的最后一个元素。这个行为的后果是程序不会立刻崩溃却可能做一次毫无意义的比较然后错误地提前退出循环。正确写法是while j 0 and arr[j] key因为Python的and是短路运算j 0为False时就不会再执行右边的比较了。坑二忘记暂存key。# 错误示例 for i in range(1, n): j i - 1 while j 0 and arr[j] arr[i]: # arr[i]会变 arr[j 1] arr[j] j - 1 arr[j 1] arr[i]这个例子特别有迷惑性。第一次比较时arr[i]确实是新牌但一旦执行arr[j1] arr[j]如果j1 iarr[i]就被覆盖了。后面的比较和最后的插入都基于已经变化的值结果必然错误。这再次说明key arr[i]不是可有可无的而是防止原始数据被移动操作破坏的安全锁。坑三循环范围写错。for i in range(n): # 多处理了 arr[0]没有必要 for i in range(1, n1): # 最后会越界range(n)会让第一个元素也参与排序虽然可能也不会报错但白白浪费一次比较。range(1, n1)则在in时访问arr[n]直接抛IndexError。写的时候记住一个口诀从不关心的第二个元素开始到最后一个有效下标结束。4.2 一个调试技巧把每一轮的状态打出来如果你在写插入排序时发现结果不对不要盯着代码干瞪眼直接在循环里加一行print看它每一轮到底做了什么def insertion_sort_debug(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 print(f 移动后: arr{arr}, j{j}, key{key}) arr[j 1] key print(f第{i}轮插入 {key}, 结果: {arr}) return arr以[5,2,4,6,1,3]为例你会在控制台看到第i轮开始时左边是如何逐步形成有序前缀的。一旦某次输出和手推不一致你就能立刻定位是移动方向错还是终止条件错。很多时候问题就出在“多移动了一个位置”或“少移动了一个位置”。4.3 边界用例和自测清单不管是在学习阶段还是面试前我都建议准备一套固定的测试用例。插入排序虽然简单但边界条件一样不能漏。def test_insertion_sort(): test_cases [ [], [1], [5, 2, 4, 6, 1, 3], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [3, 3, 3, 3], [7, -2, 0, 9, -1, 6], ] for case in test_cases: sorted_copy sorted(case) # 用Python内置排序作为标准答案 insertion_sort(case) # 原地修改 assert case sorted_copy, f失败: {case} print(全部测试通过)空列表和单元素列表考验的是循环起点是否正确完全升序和完全逆序覆盖最好/最坏情况重复元素检验稳定性包含负数和零则是常规补充。把这些用例跑一遍你的实现基本就稳了。5. 从算法到面试与工程应用5.1 面试官想听什么插入排序属于高频面试基础题但很多人只会背代码一被追问就露馅。面试官考察的从来不是你能不能默写出代码而是你是否真正理解它。我建议按下面的顺序组织回答一句话讲思路维护左侧有序区每次取右侧第一个元素从右向左找到合适位置插入。两个复杂度最好O(n)最坏和平均O(n²)额外空间O(1)。稳定性相等元素不交换是稳定排序。适用场景数据量小、基本有序、在线插入新元素时。优化延伸可以用二分查找减少比较次数但移动次数不变希尔排序就是基于间隔思想的扩展。如果面试官让你手写写完以后主动说一句“这个实现是从右往左扫描一边比较一边后移所以不需要额外的插入点数组”会显得你是真的理解代码而不是背模板。5.2 工程里插入排序不会消失很多初学者以为排序算法里只有快排、归并这些才在实际项目中使用插入排序只是教学玩具。其实大错特错。各类工业级混合排序算法几乎都会在“小规模”或“近似有序”时使用插入排序或其变体。以Python最常用的内置排序list.sort()为例它在底层实现Timsort算法能够自动识别数据中已经有序的片段run并且在对run进行合并前会对短小的run使用类似插入排序的方式整理。类似地Java的Arrays.sort()在对小数组排序时也会回退到插入排序。原因很简单当n很小的时候递归、分治、分区这些复杂操作的开销可能比插入排序的简单循环还要大。插入排序虽然渐进复杂度不高但它的常数极小在局部小规模问题上反而是最优选择之一。另外Timsort在合并run时还会利用一种类似插入排序的“Galloping Mode”能高效地把一个元素插入到另一个有序run中。所以说插入排序不是被淘汰的玩具而是现代高性能排序里沉默的基座。5.3 实战场景维护实时有序的列表假设你在做一个游戏后台的实时排行榜新分数不断推送过来你需要把新分数插入到一个已经有序的分数列表里并保持顺序正确。最简单粗暴的方式是append后再调用sort()但如果你对性能有一定要求或者想利用“基于有序数组插入”的特性完全可以用插入排序的思想手动写一个函数def insert_sorted(sorted_list, new_value): 将 new_value 插入 sorted_list升序保持有序。 这里为了直观使用的是交换式写法实际数据量较大时可以用移位法。 sorted_list.append(new_value) i len(sorted_list) - 1 while i 0 and sorted_list[i] sorted_list[i - 1]: sorted_list[i], sorted_list[i - 1] sorted_list[i - 1], sorted_list[i] i - 1 return sorted_list这个操作的时间复杂度取决于新元素在有序列表中插入的位置。如果新值通常落在末尾只需比较一次极端接近O(1)即使落在最前面也只需要移动整个列表复杂度为O(n)。相比每次重新排序O(n log n)在线插入模式下的插入排序往往更直接。类似场景还有很多比如维护一组按时间排序的日志记录、保持直播间弹幕按发送序号有序、在数据流处理中对窗口内数据做增量排序。理解了这一点你就能把“插牌”的动作迁移到很多实际代码里。以我个人的经验插入排序是一个非常奇妙的算法它足够简单让我第一次理解了“循环不变量”的含义又足够深刻能一路引申出希尔排序、Timsort这些工业级方案。如果你正在学建议不要只背代码而是拿一副扑克牌自己摸几张牌插一插再回来看Python代码很多别扭的地方一下子就通了。最后再分享一个小技巧当你需要在一个“已经有序的数组”里插入一个新元素时别急着写复杂逻辑直接回忆一遍插入排序的内层循环把后面的元素往右挪一个位置再把新元素写进去。这个动作在许多真实项目里比排序更常见。多写几次插入排序就真的长在你脑子里了。