直接插入排序：原理、Python与C实现及工程优化全解析

直接插入排序大概是被很多人口头鄙视、又偷偷用来救场的算法。我见过不少同学，说起快排、堆排头头是道，结果真在代码里遇到一个“基本有序但偶尔几条乱序”的数组，还是老老实实调了一下插入排序。原因很简单：有时候 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] i=1, key=2：5 > 2，把5右移；2 放到位置0 结果：[2, 5, 4, 6, 1, 3] i=2, key=4：5 > 4，把5右移；2 < 4，4 放到位置1 结果：[2, 4, 5, 6, 1, 3] i=3, key=6：5 < 6，不移动，6 原地不动 结果：[2, 4, 5, 6, 1, 3] i=4, key=1：6、5、4、2 依次右移，1 放到位置0 结果：[1, 2, 4, 5, 6, 3] i=5, key=3：6、5、4 依次右移，2 < 3，3 放到位置2 结果：[1, 2, 3, 4, 5, 6]

注意看 i=3 那一轮，6 已经比左边的 5 大，所以它不需要移动。这就是有序数据下插入排序近似 O(n) 的原因：每一轮只需要一次比较，效率非常高。

2.3 比较次数与移动次数：这才是性能命门

直接插入排序的复杂度不是靠背公式，而是可以一行行数出来的。假设数组长度为 n，外层循环从 i=1 到 i=n-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 复杂度不是背出来的，是数出来的

直接插入排序的时间复杂度可以总结成一张表：

空间复杂度是 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))

我机器上的数量级大致是：n=1000 时几毫秒，n=5000 时几十毫秒，n=10000 时一两百毫秒，n=50000 时要三四秒。这和 O(n²) 的趋势非常吻合：数据规模到 5 倍，时间大概到 25 倍。

但同样的 n=50000，我把数组改成“几乎有序”，只随机打乱其中几个元素，插入排序跑完连 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 >= 0：

void 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 数据规模和多寡，决定你用不用它

工程上选不选直接插入排序，我一般按下面这个标准判断：

但说句大实话，正常业务代码里不要自己造排序轮子，直接调语言标准库的排序函数就好。自己写插入排序的场景一般是：底层类库、算法题目、嵌入式开发，或者面试手撕代码。

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、不同编译器，最优阈值都会有差异。

面试如果被问到排序优化，主动提“小数组切插入排序”通常能加分，因为这说明你不只是背了快排的复杂度，还理解工程里的常数开销。

最后分享一点个人体会：直接插入排序是所有排序里“人味”最重的算法，因为它本质上就是在模拟一个人整理扑克牌的动作。越是这种简单的算法，越值得亲手写一遍，从手推模拟到代码实现再到边界测试，走完这一圈，你对数据局部性、稳定性、常数因子这些概念的理解，会比看十遍教科书都扎实。