直接插入排序大概是被很多人口头鄙视、又偷偷用来救场的算法。我见过不少同学说起快排、堆排头头是道结果真在代码里遇到一个“基本有序但偶尔几条乱序”的数组还是老老实实调了一下插入排序。原因很简单有时候 O(n²) 看起来很吓人但数据规模压到足够小、混乱程度压到足够低的时候它的实际运行速度就是能吊打那些理论复杂度更漂亮的算法。这篇文章想把“直接插入排序的简单实现”这件事一次性讲透从它为什么值得学到手工模拟完整排序过程再给出 Python 和 C 两个可运行版本然后聊聊复杂度、稳定性、优化方案最后把我实际踩过的坑摊开给你看。适合刚学数据结构的新手也适合准备面试、或者想在自己代码里加一个“小数组排序函数”的工程师。1. 为什么“最基础”的排序反而值得单独写一篇1.1 它没有你想象中那么无用直接插入排序在教材里通常只占两三页很多人看完就觉得这是个“教学演示用例”转身去追求快排、堆排这类更“高级”的算法。但工程里它无处不在JDK 的双轴快排在递归到小数组时会切换成插入排序glibc 的 qsort 在处理少量元素时也是插入排序很多嵌入式环境不允许用递归插入排序就是最省心的选择。你其实早就已经在用它了只是没有意识到。数据规模小到一定程度以后O(n²) 的常数因子可能只有 O(n log n) 算法的十分之一甚至更低。对一个 15 个元素的数组快排的递归、分区、栈帧开销远大于插入排序那几十次比较和移动。这是取舍问题不是智商问题。1.2 三个马上能用上的场景第一类近乎有序的数据流。日志、股票行情、传感器采集的数据整体有序但偶尔混入几条乱序记录用直接插入排序扫一遍就能把数据拉回正轨实际开销接近 O(n)。第二类流式在线排序。如果数据是一个个到达的每来一个就希望维护一个有序序列直接插入排序天然支持这种操作来一个元素找到位置插进去就这么简单。第三类混合排序的底层元素。写自己的排序工具库时递归到数组长度小于某个阈值10 到 20 左右就可以切换到插入排序这是很多标准库里真实存在的策略。2. 把“像整理扑克牌”这句话翻译成算法步骤2.1 已排序区、未排序区与腾位插入很多人第一次听插入排序得到的解释是“就像整理扑克牌”但这个类比太笼统真正写代码前需要把它翻译成两个明确的区域已排序区初始时只有第一个元素它在数组最左边。未排序区剩下所有元素从第二个一直到最后一个。每一轮从未排序区最前面取一个元素用key变量保存下来然后在已排序区里从右往左逐个比较。遇到比key大的元素就把这个元素往右挪一位给key腾出位置遇到第一个不大于key的元素就停止把key放进腾出来的空位。这里有个关键点插入排序做的是“腾位插入”不是“交换”。交换是冒泡的做法插入排序每轮只把一个元素往右移动一位整体移动量小得多常数因子也更低。2.2 手工跑一遍 [5, 2, 4, 6, 1, 3]我建议新手不要直接看代码先手写模拟几轮对数组变化的印象会深很多。下面这个例子完整走一遍初始[5, 2, 4, 6, 1, 3] i1, key25 2把5右移2 放到位置0 结果[2, 5, 4, 6, 1, 3] i2, key45 4把5右移2 44 放到位置1 结果[2, 4, 5, 6, 1, 3] i3, key65 6不移动6 原地不动 结果[2, 4, 5, 6, 1, 3] i4, key16、5、4、2 依次右移1 放到位置0 结果[1, 2, 4, 5, 6, 3] i5, key36、5、4 依次右移2 33 放到位置2 结果[1, 2, 3, 4, 5, 6]注意看 i3 那一轮6 已经比左边的 5 大所以它不需要移动。这就是有序数据下插入排序近似 O(n) 的原因每一轮只需要一次比较效率非常高。2.3 比较次数与移动次数这才是性能命门直接插入排序的复杂度不是靠背公式而是可以一行行数出来的。假设数组长度为 n外层循环从 i1 到 in-1一共 n-1 轮。最坏情况是数组完全逆序。第 i 轮需要把key一路比到数组最前面比较 i 次、移动 i 次。总的比较次数就是1 2 ... (n-1) n(n-1)/2移动次数同样是 n(n-1)/2。平均情况是每个位置的插入概率差不多相等比较次数约为第 i 轮的一半总数大致是 n²/4 量级所以平均复杂度也是 O(n²)。最好情况就是数组已经有序每轮只做一次比较、零次移动总比较次数只有 n-1这是 O(n) 的线性复杂度。这也是为什么“插入排序是 O(n²)”这个结论不能一概而论。它在有序、近似有序、小规模数据上的表现绝对配得上“简单实用”四个字。3. 参考实现Python 和 C 两个版本逐行讲意图3.1 Python 版本最贴近思路的写法直接插入排序的 Python 实现非常短短到很多人以为抄一遍就完事了但每一行都值得细看def insertion_sort(arr): n len(arr) for i in range(1, n): 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 arr四个关键点第一外层循环从range(1, n)开始而不是range(n)。第一个元素默认已经在已排序区从第二个元素开始插。第二key arr[i]提前保存当前要插入的值。如果不保存后面内层循环会把arr[i]覆盖掉就没法插入了。第三内层循环的条件是j 0 and arr[j] key。Python 的and是短路求值如果j 0不成立直接跳过后半段不会访问arr[-1]。这个顺序不能反。第四循环结束后j停留在第一个不大于key的位置所以插入位置是j 1。这个函数是原地排序直接修改传入的列表同时返回它。返回原列表是为了方便链式调用比如sorted_arr insertion_sort(arr)这样写。3.2 C 版本把索引和越界问题提前暴露出来C 语言的版本几乎一模一样但有一个隐藏的坑必须提前说明void insertion_sort(int a[], int n) { int i, j, key; for (i 1; i n; i) { key a[i]; j i - 1; while (j 0 a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }C 语言里很多人图省事写成while (a[j] key j 0)想着反正两个条件都要判断。但问题是的左侧先执行当j已经变成 -1 时a[j]访问的是a[-1]这是未定义行为。在 Debug 模式下可能直接崩溃在 Release 模式下可能读到栈上的脏数据排序结果看起来是“逻辑错误”极其阴险。所以 C 版本里j 0必须放在的左侧这是红线。3.3 用随机测试用例把代码“打”一遍代码写完第一件事不是跑教科书那个 [5, 2, 4, 6, 1, 3]而是写个随机测试脚本把空数组、单元素、重复元素、负数全部覆盖掉import random def test_insertion_sort(): for _ in range(2000): arr [random.randint(-100, 100) for _ in range(random.randint(0, 120))] expect sorted(arr) insertion_sort(arr) if arr ! expect: print(fail on:, arr, expect:, expect) return print(pass)跑这个脚本的时候注意一个细节insertion_sort是原地排序所以要先备份或者直接用切片传入。我见过不少人测试时写insertion_sort(arr[:])结果原数组没变判断自己代码“有问题”其实是测试写错了。排序结果对比用arr ! expect不要用is列表比较的是内容。4. 复杂度、稳定性和实测表现一次说清4.1 复杂度不是背出来的是数出来的直接插入排序的时间复杂度可以总结成一张表情况比较次数移动次数时间复杂度最好正序n-10O(n)最坏逆序n(n-1)/2n(n-1)/2O(n²)平均约 n²/4约 n²/4O(n²)空间复杂度是 O(1)因为只需要一个key变量是典型的原地排序算法。这里想多说一句面试时被问到复杂度不要只背“O(n²)”最好能说出“最好 O(n)、最坏 O(n²)、平均 O(n²)”并且能解释为什么最好情况能达到线性。这比背结论强得多。4.2 稳定性藏在“大于”和“大于等于”里直接插入排序是稳定排序。稳定是什么意思如果数组里有两个值相同的元素排序后它们的相对顺序不会改变。稳定性的关键就在内层循环那一行while arr[j] key。当遇到相等的元素时arr[j] key为假循环停止key被插到这个相等元素后面。也就是说原来在前的相等元素永远保持在前面。如果你脑子一抽改成arr[j] key相等元素会被搬走相对顺序就乱了稳定性立刻丢失。稳定排序在工程里有个典型场景先按姓名排序再按部门排序你希望部门分组后每个人在部门内部仍然保持姓名顺序。这一步只有稳定排序能保证不稳定排序会把前一轮排好的顺序打乱。4.3 一台普通电脑上的实测数量级理论归理论实际跑一跑会更有感觉。我当时用 Python 在普通笔记本上测过随机整数的排序耗时大概是这样import random import time for n in [1000, 5000, 10000, 50000]: arr [random.randint(0, 100000) for _ in range(n)] t0 time.perf_counter() insertion_sort(arr) t1 time.perf_counter() print(n, round(t1 - t0, 4))我机器上的数量级大致是n1000 时几毫秒n5000 时几十毫秒n10000 时一两百毫秒n50000 时要三四秒。这和 O(n²) 的趋势非常吻合数据规模到 5 倍时间大概到 25 倍。但同样的 n50000我把数组改成“几乎有序”只随机打乱其中几个元素插入排序跑完连 10 毫秒都不用。这就是最好情况 O(n) 的实战价值。所以选不选插入排序不能只看数据量还要看数据乱不乱。5. 三个优化方向从能跑变成好用5.1 二分插入排序砍比较次数移动次数不动标准插入排序在已排序区里是从右往左逐个比较比较平均要 n²/4 次。既然已排序区已经有序完全可以用二分查找直接定位插入位置把比较次数从 O(n²) 降到 O(n log n)。import bisect def binary_insertion_sort(arr): for i in range(1, len(arr)): key arr[i] pos bisect.bisect_right(arr, key, 0, i) for j in range(i, pos, -1): arr[j] arr[j - 1] arr[pos] key return arr这里有个稳定性细节要用bisect_right不要用bisect_left。因为bisect_left会把相等元素插到已有相等元素的前面破坏稳定性bisect_right插到右侧保证相等元素的相对顺序不变。但从实测来看二分插入排序往往比普通版本快不了多少甚至可能更慢。原因很简单插入排序的大头是移动元素不是比较。比较次数砍掉了移动次数还是 O(n²)总成本并没有质变。这也说明一个道理优化要对准真正的瓶颈。5.2 哨兵技巧理论很香工程别乱用教科书里还有个经典优化叫“哨兵位”。思路是让内层循环少判断一次j 0void insertion_sort_sentinel(int a[], int n) { int i, j, key; for (i 1; i n; i) { key a[i]; a[0] key; j i - 1; while (a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } }原理是把key复制进a[0]这样即使要插入的位置是最前面循环在j走到 0 时也会因为a[0] key而不满足a[j] key自动停下省掉了j 0的检查。这个写法有一个致命前提数组下标 0 必须是空置的哨兵位不能存真实数据。如果数组本来就是从 0 开始存数据a[0] key会直接覆盖第一个元素导致数据丢失。所以我的建议是理解思路没问题但工程代码里别这么写。省掉一次边界检查换来的是一堆内存安全隐患和可读性损失不划算。5.3 和快排打配合小数组兜底才是它的大杀器直接插入排序最实用的优化不是优化它自己而是让它在快排递归到小数组时出来兜底。原因很直接快排的递归和分区是有固定开销的数组越短这个固定开销占比越高。当数组长度降到 16 左右时快排每多递归一层可能只为十几个元素做分区收益远小于开销。这时候插入排序的平方项因为 n 太小根本构不成威胁。写排序工具库时可以这样设计def hybrid_sort(arr): if len(arr) 16: insertion_sort(arr) return arr # 此处接快排或归并主体逻辑有些标准库把阈值定在 16有些定在 47甚至有的在 64 左右。这个数值不需要死记在自己机器上多测几组就能找到最优值。我实测下来阈值在 12 到 24 之间通常是安全区间。6. 边界情况与真实工程里的判断标准6.1 空数组、单元素、重复数据这些“送分题”很多实现写完之后只测了一个正常数组然后信心满满地提交了。实际上边界情况才是翻车高发区。空数组和单元素数组外层循环天然不执行或者只处理一次代码一般不会出错但一定要在测试用例里写上否则你永远不知道以后哪次改动会把范围算错。重复数据这一点容易被忽略。我用的是arr[j] key所以大量重复数据时相等元素不参与移动性能接近有序情况。这是个反直觉的优点数据越“重复”直接插入排序表现越好。逆序数据这是最坏情况性能断崖式下降。如果面试官问“插入排序的敌人是什么”答案就是逆序大数组。6.2 数据规模和多寡决定你用不用它工程上选不选直接插入排序我一般按下面这个标准判断数据规模数据形态是否推荐n 16任意推荐n 1000近似有序推荐n 1000随机可用但标准库排序通常更快n 10000随机不推荐但说句大实话正常业务代码里不要自己造排序轮子直接调语言标准库的排序函数就好。自己写插入排序的场景一般是底层类库、算法题目、嵌入式开发或者面试手撕代码。6.3 链表场景为什么数组版本反而更省心有人会说链表不是更适合插入吗插入一个节点只要改指针O(1) 搞定。理论上没错但要考虑完整过程链表插入排序每轮需要从头遍历找到正确位置查找本身是 O(n)整体复杂度仍然是 O(n²)。而且数组版本的“移动”是连续内存里的整体挪动现代 CPU 对连续内存的访问效率非常高大大弥补了移动的代价。链表是跳跃式访问内存缓存命中率低常数因子反而更大。所以绝大多数情况下数组版插入排序更省心。面试让你写链表插入排序是另一回事那是考指针操作另当别论。7. 我在实现和调试中踩过的坑7.1 越界判断的顺序写反一次就崩一次我自己一度写过这样的 C 代码while (a[j] key j 0) { ... }当时数组长度很小恰好a[-1]读到的脏数据不大于key循环直接退出程序没崩但排序结果时对时错。我以为是算法哪里写错了对着代码反复看最后用 Address Sanitizer 才定位到是越界访问。从那以后我对这个顺序格外敏感j 0永远写在左边无论 Python 还是 C。7.2 把“腾位移动”写成了“相邻交换”还有一次我图省事写成这样def wrong_insertion_sort(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这段代码也能排序但它已经不是标准的直接插入排序了。每次“交换”需要三次赋值最坏情况下总赋值次数是 3n(n-1)/2比标准插入排序的 n(n-1)/2 多了三倍。更要命的是它改变了算法结构让“将有序元素后移一次”这个核心优势完全消失。写插入排序时脑子里要时刻清楚移动是单向的、一次一格的而不是两两交换。7.3 几个值得长期记住的经验自己实现排序时一定要跑随机测试和边界测试不要只测教科书上的例子。组合排序时阈值要实测不要迷信网上说的 16 或者 47不同语言、不同CPU、不同编译器最优阈值都会有差异。面试如果被问到排序优化主动提“小数组切插入排序”通常能加分因为这说明你不只是背了快排的复杂度还理解工程里的常数开销。最后分享一点个人体会直接插入排序是所有排序里“人味”最重的算法因为它本质上就是在模拟一个人整理扑克牌的动作。越是这种简单的算法越值得亲手写一遍从手推模拟到代码实现再到边界测试走完这一圈你对数据局部性、稳定性、常数因子这些概念的理解会比看十遍教科书都扎实。