把一张新扑克牌插到手里已经排好序的牌中间这就是插入排序。它可能是所有排序算法里最接近人类直觉的一个不需要先看完全部数据也不需要递归和分治只需要“把新元素往已经有序的部分里找一个合适位置插进去”。很多零基础读者第一次接触排序算法时会觉得快排、归并很抽象但插入排序几乎可以用一副扑克牌讲清楚。这篇文章会从零开始拆解插入排序的完整执行过程用“动画帧”级别的表格还原每一步比较和移动同时给出可直接运行的 Python 实现、折半插入排序扩展、可视化脚本和常见性能观察。不管你是准备数据结构考试、刷算法题还是只是想彻底搞懂排序算法这篇文章都可以直接收藏。1. 核心能力速览能力项说明算法类型比较类内部排序、原地排序时间复杂度最好 O(n)平均 O(n²)最坏 O(n²)空间复杂度O(1)额外空间不随数据量增长稳定性稳定相等元素的相对顺序不会改变排序方式逐个将元素插入到左侧有序区适合数据规模小规模数据或者基本有序的数据最优改进折半插入排序、希尔排序可视化友好度极高适合做动画演示和零基础教学应用场景教学示例、在线增量插入、小规模排序、部分高级排序的底层优化插入排序最容易被忽视的优点不是快而是“直接”和“稳定”。它不需要额外数组不需要复杂递归代码量很短非常适合作为排序算法入门的第一个算法。它也是后续理解折半插入排序、希尔排序以及分析算法复杂度的重要基础。2. 适用场景与使用边界插入排序适合谁首先是很适合数据结构初学者。它的循环逻辑比冒泡排序更容易读懂比选择排序更接近真实世界的排序行为。第二个适合的场景是“数据量不大但变化频繁”的场景比如实时维护一个排行榜、向有序列表里逐条插入新记录。第三个场景是数据本身已经接近有序这时插入排序会退化成近似 O(n)效率反而比快排和归并更好。它不适合什么场景数据量一旦达到几万、几十万甚至百万级并且数据乱序严重插入排序的 O(n²) 复杂度会很快拖垮性能。此时应该优先使用快速排序、归并排序、堆排序或者语言内置的排序方法。另一个容易踩坑的地方是插入排序虽然稳定但如果代码里把比较符号写成arr[j] key稳定性就会被破坏相等的元素会交换位置这一点在练习时需要特别注意。从工程边界来看插入排序本身是一个通用算法没有版权和授权风险。但在真实业务系统里如果排序的数据包含用户手机号、身份证号、订单金额等敏感信息排序代码虽然只做内存操作但打印日志、输出中间结果时要注意脱敏不能因为调试把完整敏感数据写到日志文件或可视化界面中。本文所有示例都以教学和本地测试为目的请勿将含个人隐私的数据上传到不受控制的在线演示平台。3. 环境准备与前置条件本教程主要使用 Python 编写插入排序、折半插入排序和动画演示推荐环境如下。项目建议操作系统Windows / macOS / Linux 均可Python 版本Python 3.8 及以上必要依赖matplotlib用于柱状图动画推荐环境本地虚拟环境或 Jupyter NotebookIDEVS Code / PyCharm / 任意文本编辑器安装依赖前先确认 Python 环境可用。在终端执行python --version如果命令提示找不到python在 Windows 上可以试试python3 --version然后安装 matplotlibpip install matplotlib如果下载速度慢可以临时使用国内镜像源pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple使用 Jupyter Notebook 的同学还可以在代码开头加入%matplotlib inline让动画图直接显示在单元格下方。不过动画功能在本地脚本中表现更稳定本文后面的可视化代码建议保存为.py文件运行。4. 安装部署与启动方式这里不是传统意义上的“项目部署”而是把排序脚本组织成一个可运行的小工程。推荐目录结构如下sort-demo/ ├── sort_algorithms.py ├── animate_sort.py └── test_sort.py创建虚拟环境并激活避免污染全局 Pythonmkdir sort-demo cd sort-demo python -m venv venvWindows 激活venv\Scripts\activatemacOS / Linux 激活source venv/bin/activate激活后安装依赖pip install matplotlib将算法实现写入sort_algorithms.pydef 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 arr启动一个最简单的测试# test_sort.py from sort_algorithms import insertion_sort data [5, 2, 4, 6, 1, 3] print(insertion_sort(data))运行python test_sort.py预期输出[1, 2, 3, 4, 5, 6]到这里插入排序的基本代码就跑通了。后面会进一步拆解它到底是怎么一步步排序的。5. 插入排序动画拆解逐步看每一轮很多读者看代码能看懂但一到时间复杂度和稳定性分析就晕。问题往往出在“没有在脑子里模拟过程”。下面用动画拆解的方式把数组[5, 2, 4, 6, 1, 3]的每一轮变化完整展开。初始状态把第 0 个元素5看成已经有序区其余元素[2, 4, 6, 1, 3]是未排序区。轮次当前数组状态待插入元素 key动作说明初始[5, 2, 4, 6, 1, 3]无左侧有序区只有 5第1轮[5, 2, 4, 6, 1, 3]22 与 5 比较5 后移一位2 插入到位置 0第1轮结果[2, 5, 4, 6, 1, 3]无有序区变成 [2, 5]第2轮[2, 5, 4, 6, 1, 3]44 与 5 比较5 后移4 再与 2 比较停在位置 1第2轮结果[2, 4, 5, 6, 1, 3]无有序区变成 [2, 4, 5]第3轮[2, 4, 5, 6, 1, 3]66 与 5 比较6 大于 5不需要移动第3轮结果[2, 4, 5, 6, 1, 3]无有序区变成 [2, 4, 5, 6]第4轮[2, 4, 5, 6, 1, 3]11 依次与 6、5、4、2 比较所有大于 1 的元素全部后移第4轮结果[1, 2, 4, 5, 6, 3]无有序区变成 [1, 2, 4, 5, 6]第5轮[1, 2, 4, 5, 6, 3]33 与 6、5、4 比较这三个元素后移3 插入到位置 2第5轮结果[1, 2, 3, 4, 5, 6]无排序完成从动画视角看左侧的有序区像一个不断变长的牌堆右侧的未排序区像一个待处理的牌堆。每一轮只做两件事从右侧取第一张牌把它插入左侧牌堆的正确位置。这里特别要注意插入排序不是“交换”而是“移动 插入”。很多初学冒泡排序后再学插入排序容易把代码写成不断交换相邻元素。交换写法也能排序但会丢失插入排序“记录 key 后整体移动”的直觉也会让移动次数变得难以理解。正确写法是先把待插入元素存到变量key中然后向左扫描凡是比key大的元素都向右移动一格最后把key放到空出来的位置。6. 插入排序代码实现与边界测试先看标准实现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 arr这段代码的边界条件有两个重点range(1, len(arr))保证从第二个元素开始处理因为第一个元素天然有序。while j 0加上and arr[j] key两者顺序不能反。如果写成arr[j] key and j 0当j变成-1时Python 会先访问arr[-1]导致最后一次比较拿到数组末尾元素产生错误结果。建议写一组边界测试确保代码不是只对一个例子有效from sort_algorithms import insertion_sort def test_insertion_sort(): assert insertion_sort([]) [] assert insertion_sort([1]) [1] assert insertion_sort([5, 4, 3, 2, 1]) [1, 2, 3, 4, 5] assert insertion_sort([1, 2, 3, 4, 5]) [1, 2, 3, 4, 5] assert insertion_sort([3, 1, 3, 2, 1]) [1, 1, 2, 3, 3] assert insertion_sort([2, 2, 2, 2]) [2, 2, 2, 2] print(所有边界测试通过) test_insertion_sort()这里的重复元素测试非常关键。当数组已经包含相同元素时使用而不是可以保证后续出现的相同元素不会被移动到已出现的相同元素之前这就是稳定性。如果排序结果只在数值上正确但相同元素的前后顺序被打乱就不能称为稳定排序。运行上面的测试预期输出所有边界测试通过如果某个用例报错优先检查 while 条件里的条件是还是以及j 1是否写成了j。7. 折半插入排序减少比较次数插入排序在寻找插入位置时采用的是线性扫描。但左侧已经是有序区所以完全可以使用二分查找快速定位插入位置。这种优化叫做折半插入排序也叫二分插入排序。它把查找时间从 O(n) 降到 O(log n)但元素移动次数仍然是 O(n)所以最坏时间复杂度依然是 O(n²)。def binary_insertion_sort(arr): for i in range(1, len(arr)): key arr[i] low, high 0, i - 1 while low high: mid (low high) // 2 if arr[mid] key: low mid 1 else: high mid - 1 for j in range(i, low, -1): arr[j] arr[j - 1] arr[low] key return arr这里最关键的是二分查找结束后的插入位置low。当循环结束时low指向第一个大于等于key的位置或者指向i本身。然后从i开始把[low, i-1]范围内的元素整体向右移动一格最后把key写入arr[low]。为什么查找条件使用arr[mid] key而不是因为当arr[mid] key时我们希望继续向右查找让新元素插入到已有相同元素的后面这样折半插入排序也能保持稳定。如果你把条件改成相等元素会插入到已有相同元素的前面稳定性就被破坏了。折半插入排序并不是在所有情况下都比普通插入排序快。它减少的是比较次数移动次数没有减少。对于整数数组这种比较成本很低的数据两者差距不明显。但如果你排序的是字符串、对象或结构体比较操作成本较高时折半插入排序的优化效果就值得考虑。8. 用 Matplotlib 画插入排序动画“动画拆解”不只是用表格还可以直接用代码画出柱状图动画。这个脚本会记录每一轮排序后的数组状态然后用柱状图逐帧播放视觉上非常直观。import matplotlib.pyplot as plt def insertion_sort_with_steps(arr): steps [] a arr.copy() steps.append(a.copy()) for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key steps.append(a.copy()) return steps def animate_insertion_sort(arr, interval0.8): steps insertion_sort_with_steps(arr) plt.ion() fig, ax plt.subplots(figsize(8, 4)) for index, step in enumerate(steps): ax.clear() ax.bar(range(len(step)), step, colorsteelblue) ax.set_title(fInsertion Sort - Step {index}) ax.set_xlabel(Index) ax.set_ylabel(Value) ax.set_ylim(0, max(arr) 2) for x, v in enumerate(step): ax.text(x, v 0.2, str(v), hacenter, fontsize10) plt.draw() plt.pause(interval) plt.ioff() plt.show() if __name__ __main__: data [5, 2, 4, 6, 1, 3] animate_insertion_sort(data)运行脚本python animate_sort.py你会看到每一轮结束后柱子高度发生变化左侧的柱子逐渐变成有序状态。如果想看更细的“移动过程”需要在每个移动步骤内部也插入一帧上面代码只记录了每轮结束后的状态。对于零基础理解来说记录每轮结束状态已经足够不会造成视觉混乱。如果使用 Jupyter Notebook可以在导入 matplotlib 后加上%matplotlib inline但 Jupyter 对实时动画的支持不如脚本流畅。如果动画窗口一闪而过可以在脚本末尾加上input(按回车退出)防止窗口自动关闭。对于较大的数组比如超过 30 个元素每一帧都重绘柱状图会让动画明显卡顿建议只对 6 到 15 个元素做动画演示。9. 函数接口与批量测试思路插入排序通常不是独立服务而是作为函数嵌入到业务代码中。它对外暴露的是一个“输入数组返回有序数组”的函数接口。在工程上可以这样封装def sort_array(arr, inplaceTrue): if inplace: insertion_sort(arr) return arr else: return insertion_sort(arr.copy())如果业务中需要批量排序很多个小数组可以用循环逐个处理并记录耗时import random import time from sort_algorithms import insertion_sort def batch_test(sizes): for size in sizes: data [random.randint(0, 10000) for _ in range(size)] start time.perf_counter() insertion_sort(data) cost time.perf_counter() - start print(fsize{size:6}, time{cost:.5f}s) batch_test([10, 100, 1000, 5000])注意不同机器运行耗时差异很大不要在文档里写死“1000 个元素需要多少秒”。批量测试的重点是比较不同数据规模下的增长趋势数据量从 1000 涨到 5000大约 5 倍但耗时可能增长远不止 5 倍这正是 O(n²) 复杂度的直观体现。更严谨的做法是多次运行取平均值并且对同一规模随机生成多组数据避免某一次数据分布对结果产生干扰。比如很多语言自带的有序或近乎有序数据会让插入排序进入最好情况 O(n)导致测试结果失真。10. 资源占用与性能观察插入排序是一个非常省内存的排序算法。它始终在原数组上操作不需要额外数组所以空间复杂度是 O(1)。无论排序 10 个元素还是 10000 个元素额外内存都只占用一个key变量和几个下标变量。时间复杂度需要分情况看最好情况数据已经有序每一轮只需要比较一次内层 while 不进入因此时间复杂度 O(n)。最坏情况数据逆序每一轮都要把前面所有元素后移比较次数和移动次数都达到最大时间复杂度 O(n²)。平均情况可以看成一半元素需要移动一半长度整体也是 O(n²)。在动画演示里最影响性能的不是排序本身而是 matplotlib 的逐帧重绘。数据量在 20 个以内时动画流畅度很好数据量超过 50 个后重绘开销会明显变大。写可视化时可以通过降低interval、减少柱子上的文本标注、或者只绘制部分步数来优化。在真实排序场景里如何观察排序性能最直接的方法是time.perf_counter()记录耗时同时统计比较次数和移动次数def insertion_sort_with_count(arr): compare_count 0 move_count 0 for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: compare_count 1 arr[j 1] arr[j] move_count 1 j - 1 if j 0: compare_count 1 arr[j 1] key move_count 1 return arr, compare_count, move_count统计次数比耗时更稳定因为不依赖机器性能。逆序数组的比较次数和移动次数最多有序数组最少随机数组居中。通过这个工具可以把复杂度的“抽象结论”变成一组看得见的数字。11. 常见问题与排查方法问题现象可能原因排查方式解决方案空数组排序后报错for 循环或函数试图访问下标打印len(arr)和下标插入排序天然支持空数组检查代码是否写死了arr[0]单元素数组返回错误外层 range 起点写成了 0检查for i in range(1, len(arr))从 1 开始确保只处理未排序区结果多出或缺失元素key赋值位置错误每轮打印数组状态保证每轮先保存key再次赋值回去数据量大时非常慢对大规模随机数组使用了插入排序用time.perf_counter()统计耗时数据量大时更换快排、归并或内置排序动画窗口一闪而过脚本执行结束后窗口自动关闭在plt.show()前等待加input(按回车退出)matplotlib 中文乱码系统缺少中文字体检查绘图文本是否包含中文设置plt.rcParams[font.sans-serif] [SimHei]或改用英文标题二分插入排序死循环二分查找条件写成low high且更新规则不对打印每轮 low/high使用while low high并对mid分情况更新稳定性测试失败while 条件使用打印相同元素排序前后顺序改用保持相等元素原有顺序插入排序最容易写错的地方就是内层 while 的边界顺序。初学者常常把j 0写到arr[j] key后面导致取到arr[-1]。再一个容易踩坑的是把arr[j 1] arr[j]写成arr[j] arr[j - 1]这样移动方向会反结果会出现重复或覆盖问题。遇到这种问题不要只看最终结果直接在循环里print(arr)一步一步对比动画帧。12. 最佳实践与使用建议如果你正在学习数据结构建议按照下面的顺序练习插入排序先不看代码用扑克牌手动排序 5 张牌感受“移动 插入”的过程。写出第一版插入排序用[5, 2, 4, 6, 1, 3]逐轮验证。补充边界测试空数组、单元素、逆序、完全有序、重复元素。自己画出每一轮数组状态和动画脚本输出对比。加上比较次数和移动次数统计体会最坏情况和最好情况。写一遍折半插入排序确认二分查找后的low就是插入位置。用一张大随机数组测试两种插入排序确认性能差异并不大。如果还有精力继续学希尔排序看它如何通过分组减少移动次数。在工程中插入排序不一定是主角但经常作为“组合拳”的一部分出现。很多快排实现会在递归区间长度小于某个阈值时切到插入排序因为此时数据已经接近有序插入排序的开销比继续递归更小。这是非常经典的生产级优化策略。理解插入排序对读懂这类源码很有帮助。动画化排序算法时建议只对 8 到 15 个元素做演示步间间隔控制在 0.5 秒到 1 秒之间。颜色上可以用灰色表示已排序区红色高亮当前的 key蓝色表示待排序区。这样的视觉层次比所有柱子一种颜色要清楚得多。也可以把每个元素的值标在柱子上方便对照表格理解。13. 总结与下一步插入排序最值得尝试的点是“用手推一遍整个过程”。它没有复杂的数学推导也不需要额外的空间代码写出来只有十几行。第一次上手时先拿[5, 2, 4, 6, 1, 3]这样的数组做动画拆解把每一轮数组状态写出来再对照代码逐行看基本十分钟就能吃透。最先应该验证的是逆序数组和完全有序数组。逆序数组会让插入排序进入最坏情况完全有序数组则会让它进入最好情况两者的比较次数差异非常明显。最容易踩的坑是 while 条件里j 0的顺序以及比较符号写成导致排序不稳定。下一步可以沿着两条线继续深入一条是折半插入排序和希尔排序看如何从“减少移动”和“减少比较”两个方向优化插入排序另一条是学习归并排序和快速排序把它们的时间复杂度 O(n log n) 与插入排序的 O(n²) 放在一起对比会更直观地理解规模化排序为什么需要更高级的算法。排序算法是数据结构的基本功插入排序则是这扇门最好推开的第一扇窗。
把一张新扑克牌插到手里已经排好序的牌中间这就是插入排序。它可能是所有排序算法里最接近人类直觉的一个不需要先看完全部数据也不需要递归和分治只需要“把新元素往已经有序的部分里找一个合适位置插进去”。很多零基础读者第一次接触排序算法时会觉得快排、归并很抽象但插入排序几乎可以用一副扑克牌讲清楚。这篇文章会从零开始拆解插入排序的完整执行过程用“动画帧”级别的表格还原每一步比较和移动同时给出可直接运行的 Python 实现、折半插入排序扩展、可视化脚本和常见性能观察。不管你是准备数据结构考试、刷算法题还是只是想彻底搞懂排序算法这篇文章都可以直接收藏。1. 核心能力速览能力项说明算法类型比较类内部排序、原地排序时间复杂度最好 O(n)平均 O(n²)最坏 O(n²)空间复杂度O(1)额外空间不随数据量增长稳定性稳定相等元素的相对顺序不会改变排序方式逐个将元素插入到左侧有序区适合数据规模小规模数据或者基本有序的数据最优改进折半插入排序、希尔排序可视化友好度极高适合做动画演示和零基础教学应用场景教学示例、在线增量插入、小规模排序、部分高级排序的底层优化插入排序最容易被忽视的优点不是快而是“直接”和“稳定”。它不需要额外数组不需要复杂递归代码量很短非常适合作为排序算法入门的第一个算法。它也是后续理解折半插入排序、希尔排序以及分析算法复杂度的重要基础。2. 适用场景与使用边界插入排序适合谁首先是很适合数据结构初学者。它的循环逻辑比冒泡排序更容易读懂比选择排序更接近真实世界的排序行为。第二个适合的场景是“数据量不大但变化频繁”的场景比如实时维护一个排行榜、向有序列表里逐条插入新记录。第三个场景是数据本身已经接近有序这时插入排序会退化成近似 O(n)效率反而比快排和归并更好。它不适合什么场景数据量一旦达到几万、几十万甚至百万级并且数据乱序严重插入排序的 O(n²) 复杂度会很快拖垮性能。此时应该优先使用快速排序、归并排序、堆排序或者语言内置的排序方法。另一个容易踩坑的地方是插入排序虽然稳定但如果代码里把比较符号写成arr[j] key稳定性就会被破坏相等的元素会交换位置这一点在练习时需要特别注意。从工程边界来看插入排序本身是一个通用算法没有版权和授权风险。但在真实业务系统里如果排序的数据包含用户手机号、身份证号、订单金额等敏感信息排序代码虽然只做内存操作但打印日志、输出中间结果时要注意脱敏不能因为调试把完整敏感数据写到日志文件或可视化界面中。本文所有示例都以教学和本地测试为目的请勿将含个人隐私的数据上传到不受控制的在线演示平台。3. 环境准备与前置条件本教程主要使用 Python 编写插入排序、折半插入排序和动画演示推荐环境如下。项目建议操作系统Windows / macOS / Linux 均可Python 版本Python 3.8 及以上必要依赖matplotlib用于柱状图动画推荐环境本地虚拟环境或 Jupyter NotebookIDEVS Code / PyCharm / 任意文本编辑器安装依赖前先确认 Python 环境可用。在终端执行python --version如果命令提示找不到python在 Windows 上可以试试python3 --version然后安装 matplotlibpip install matplotlib如果下载速度慢可以临时使用国内镜像源pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple使用 Jupyter Notebook 的同学还可以在代码开头加入%matplotlib inline让动画图直接显示在单元格下方。不过动画功能在本地脚本中表现更稳定本文后面的可视化代码建议保存为.py文件运行。4. 安装部署与启动方式这里不是传统意义上的“项目部署”而是把排序脚本组织成一个可运行的小工程。推荐目录结构如下sort-demo/ ├── sort_algorithms.py ├── animate_sort.py └── test_sort.py创建虚拟环境并激活避免污染全局 Pythonmkdir sort-demo cd sort-demo python -m venv venvWindows 激活venv\Scripts\activatemacOS / Linux 激活source venv/bin/activate激活后安装依赖pip install matplotlib将算法实现写入sort_algorithms.pydef 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 arr启动一个最简单的测试# test_sort.py from sort_algorithms import insertion_sort data [5, 2, 4, 6, 1, 3] print(insertion_sort(data))运行python test_sort.py预期输出[1, 2, 3, 4, 5, 6]到这里插入排序的基本代码就跑通了。后面会进一步拆解它到底是怎么一步步排序的。5. 插入排序动画拆解逐步看每一轮很多读者看代码能看懂但一到时间复杂度和稳定性分析就晕。问题往往出在“没有在脑子里模拟过程”。下面用动画拆解的方式把数组[5, 2, 4, 6, 1, 3]的每一轮变化完整展开。初始状态把第 0 个元素5看成已经有序区其余元素[2, 4, 6, 1, 3]是未排序区。轮次当前数组状态待插入元素 key动作说明初始[5, 2, 4, 6, 1, 3]无左侧有序区只有 5第1轮[5, 2, 4, 6, 1, 3]22 与 5 比较5 后移一位2 插入到位置 0第1轮结果[2, 5, 4, 6, 1, 3]无有序区变成 [2, 5]第2轮[2, 5, 4, 6, 1, 3]44 与 5 比较5 后移4 再与 2 比较停在位置 1第2轮结果[2, 4, 5, 6, 1, 3]无有序区变成 [2, 4, 5]第3轮[2, 4, 5, 6, 1, 3]66 与 5 比较6 大于 5不需要移动第3轮结果[2, 4, 5, 6, 1, 3]无有序区变成 [2, 4, 5, 6]第4轮[2, 4, 5, 6, 1, 3]11 依次与 6、5、4、2 比较所有大于 1 的元素全部后移第4轮结果[1, 2, 4, 5, 6, 3]无有序区变成 [1, 2, 4, 5, 6]第5轮[1, 2, 4, 5, 6, 3]33 与 6、5、4 比较这三个元素后移3 插入到位置 2第5轮结果[1, 2, 3, 4, 5, 6]无排序完成从动画视角看左侧的有序区像一个不断变长的牌堆右侧的未排序区像一个待处理的牌堆。每一轮只做两件事从右侧取第一张牌把它插入左侧牌堆的正确位置。这里特别要注意插入排序不是“交换”而是“移动 插入”。很多初学冒泡排序后再学插入排序容易把代码写成不断交换相邻元素。交换写法也能排序但会丢失插入排序“记录 key 后整体移动”的直觉也会让移动次数变得难以理解。正确写法是先把待插入元素存到变量key中然后向左扫描凡是比key大的元素都向右移动一格最后把key放到空出来的位置。6. 插入排序代码实现与边界测试先看标准实现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 arr这段代码的边界条件有两个重点range(1, len(arr))保证从第二个元素开始处理因为第一个元素天然有序。while j 0加上and arr[j] key两者顺序不能反。如果写成arr[j] key and j 0当j变成-1时Python 会先访问arr[-1]导致最后一次比较拿到数组末尾元素产生错误结果。建议写一组边界测试确保代码不是只对一个例子有效from sort_algorithms import insertion_sort def test_insertion_sort(): assert insertion_sort([]) [] assert insertion_sort([1]) [1] assert insertion_sort([5, 4, 3, 2, 1]) [1, 2, 3, 4, 5] assert insertion_sort([1, 2, 3, 4, 5]) [1, 2, 3, 4, 5] assert insertion_sort([3, 1, 3, 2, 1]) [1, 1, 2, 3, 3] assert insertion_sort([2, 2, 2, 2]) [2, 2, 2, 2] print(所有边界测试通过) test_insertion_sort()这里的重复元素测试非常关键。当数组已经包含相同元素时使用而不是可以保证后续出现的相同元素不会被移动到已出现的相同元素之前这就是稳定性。如果排序结果只在数值上正确但相同元素的前后顺序被打乱就不能称为稳定排序。运行上面的测试预期输出所有边界测试通过如果某个用例报错优先检查 while 条件里的条件是还是以及j 1是否写成了j。7. 折半插入排序减少比较次数插入排序在寻找插入位置时采用的是线性扫描。但左侧已经是有序区所以完全可以使用二分查找快速定位插入位置。这种优化叫做折半插入排序也叫二分插入排序。它把查找时间从 O(n) 降到 O(log n)但元素移动次数仍然是 O(n)所以最坏时间复杂度依然是 O(n²)。def binary_insertion_sort(arr): for i in range(1, len(arr)): key arr[i] low, high 0, i - 1 while low high: mid (low high) // 2 if arr[mid] key: low mid 1 else: high mid - 1 for j in range(i, low, -1): arr[j] arr[j - 1] arr[low] key return arr这里最关键的是二分查找结束后的插入位置low。当循环结束时low指向第一个大于等于key的位置或者指向i本身。然后从i开始把[low, i-1]范围内的元素整体向右移动一格最后把key写入arr[low]。为什么查找条件使用arr[mid] key而不是因为当arr[mid] key时我们希望继续向右查找让新元素插入到已有相同元素的后面这样折半插入排序也能保持稳定。如果你把条件改成相等元素会插入到已有相同元素的前面稳定性就被破坏了。折半插入排序并不是在所有情况下都比普通插入排序快。它减少的是比较次数移动次数没有减少。对于整数数组这种比较成本很低的数据两者差距不明显。但如果你排序的是字符串、对象或结构体比较操作成本较高时折半插入排序的优化效果就值得考虑。8. 用 Matplotlib 画插入排序动画“动画拆解”不只是用表格还可以直接用代码画出柱状图动画。这个脚本会记录每一轮排序后的数组状态然后用柱状图逐帧播放视觉上非常直观。import matplotlib.pyplot as plt def insertion_sort_with_steps(arr): steps [] a arr.copy() steps.append(a.copy()) for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key steps.append(a.copy()) return steps def animate_insertion_sort(arr, interval0.8): steps insertion_sort_with_steps(arr) plt.ion() fig, ax plt.subplots(figsize(8, 4)) for index, step in enumerate(steps): ax.clear() ax.bar(range(len(step)), step, colorsteelblue) ax.set_title(fInsertion Sort - Step {index}) ax.set_xlabel(Index) ax.set_ylabel(Value) ax.set_ylim(0, max(arr) 2) for x, v in enumerate(step): ax.text(x, v 0.2, str(v), hacenter, fontsize10) plt.draw() plt.pause(interval) plt.ioff() plt.show() if __name__ __main__: data [5, 2, 4, 6, 1, 3] animate_insertion_sort(data)运行脚本python animate_sort.py你会看到每一轮结束后柱子高度发生变化左侧的柱子逐渐变成有序状态。如果想看更细的“移动过程”需要在每个移动步骤内部也插入一帧上面代码只记录了每轮结束后的状态。对于零基础理解来说记录每轮结束状态已经足够不会造成视觉混乱。如果使用 Jupyter Notebook可以在导入 matplotlib 后加上%matplotlib inline但 Jupyter 对实时动画的支持不如脚本流畅。如果动画窗口一闪而过可以在脚本末尾加上input(按回车退出)防止窗口自动关闭。对于较大的数组比如超过 30 个元素每一帧都重绘柱状图会让动画明显卡顿建议只对 6 到 15 个元素做动画演示。9. 函数接口与批量测试思路插入排序通常不是独立服务而是作为函数嵌入到业务代码中。它对外暴露的是一个“输入数组返回有序数组”的函数接口。在工程上可以这样封装def sort_array(arr, inplaceTrue): if inplace: insertion_sort(arr) return arr else: return insertion_sort(arr.copy())如果业务中需要批量排序很多个小数组可以用循环逐个处理并记录耗时import random import time from sort_algorithms import insertion_sort def batch_test(sizes): for size in sizes: data [random.randint(0, 10000) for _ in range(size)] start time.perf_counter() insertion_sort(data) cost time.perf_counter() - start print(fsize{size:6}, time{cost:.5f}s) batch_test([10, 100, 1000, 5000])注意不同机器运行耗时差异很大不要在文档里写死“1000 个元素需要多少秒”。批量测试的重点是比较不同数据规模下的增长趋势数据量从 1000 涨到 5000大约 5 倍但耗时可能增长远不止 5 倍这正是 O(n²) 复杂度的直观体现。更严谨的做法是多次运行取平均值并且对同一规模随机生成多组数据避免某一次数据分布对结果产生干扰。比如很多语言自带的有序或近乎有序数据会让插入排序进入最好情况 O(n)导致测试结果失真。10. 资源占用与性能观察插入排序是一个非常省内存的排序算法。它始终在原数组上操作不需要额外数组所以空间复杂度是 O(1)。无论排序 10 个元素还是 10000 个元素额外内存都只占用一个key变量和几个下标变量。时间复杂度需要分情况看最好情况数据已经有序每一轮只需要比较一次内层 while 不进入因此时间复杂度 O(n)。最坏情况数据逆序每一轮都要把前面所有元素后移比较次数和移动次数都达到最大时间复杂度 O(n²)。平均情况可以看成一半元素需要移动一半长度整体也是 O(n²)。在动画演示里最影响性能的不是排序本身而是 matplotlib 的逐帧重绘。数据量在 20 个以内时动画流畅度很好数据量超过 50 个后重绘开销会明显变大。写可视化时可以通过降低interval、减少柱子上的文本标注、或者只绘制部分步数来优化。在真实排序场景里如何观察排序性能最直接的方法是time.perf_counter()记录耗时同时统计比较次数和移动次数def insertion_sort_with_count(arr): compare_count 0 move_count 0 for i in range(1, len(arr)): key arr[i] j i - 1 while j 0 and arr[j] key: compare_count 1 arr[j 1] arr[j] move_count 1 j - 1 if j 0: compare_count 1 arr[j 1] key move_count 1 return arr, compare_count, move_count统计次数比耗时更稳定因为不依赖机器性能。逆序数组的比较次数和移动次数最多有序数组最少随机数组居中。通过这个工具可以把复杂度的“抽象结论”变成一组看得见的数字。11. 常见问题与排查方法问题现象可能原因排查方式解决方案空数组排序后报错for 循环或函数试图访问下标打印len(arr)和下标插入排序天然支持空数组检查代码是否写死了arr[0]单元素数组返回错误外层 range 起点写成了 0检查for i in range(1, len(arr))从 1 开始确保只处理未排序区结果多出或缺失元素key赋值位置错误每轮打印数组状态保证每轮先保存key再次赋值回去数据量大时非常慢对大规模随机数组使用了插入排序用time.perf_counter()统计耗时数据量大时更换快排、归并或内置排序动画窗口一闪而过脚本执行结束后窗口自动关闭在plt.show()前等待加input(按回车退出)matplotlib 中文乱码系统缺少中文字体检查绘图文本是否包含中文设置plt.rcParams[font.sans-serif] [SimHei]或改用英文标题二分插入排序死循环二分查找条件写成low high且更新规则不对打印每轮 low/high使用while low high并对mid分情况更新稳定性测试失败while 条件使用打印相同元素排序前后顺序改用保持相等元素原有顺序插入排序最容易写错的地方就是内层 while 的边界顺序。初学者常常把j 0写到arr[j] key后面导致取到arr[-1]。再一个容易踩坑的是把arr[j 1] arr[j]写成arr[j] arr[j - 1]这样移动方向会反结果会出现重复或覆盖问题。遇到这种问题不要只看最终结果直接在循环里print(arr)一步一步对比动画帧。12. 最佳实践与使用建议如果你正在学习数据结构建议按照下面的顺序练习插入排序先不看代码用扑克牌手动排序 5 张牌感受“移动 插入”的过程。写出第一版插入排序用[5, 2, 4, 6, 1, 3]逐轮验证。补充边界测试空数组、单元素、逆序、完全有序、重复元素。自己画出每一轮数组状态和动画脚本输出对比。加上比较次数和移动次数统计体会最坏情况和最好情况。写一遍折半插入排序确认二分查找后的low就是插入位置。用一张大随机数组测试两种插入排序确认性能差异并不大。如果还有精力继续学希尔排序看它如何通过分组减少移动次数。在工程中插入排序不一定是主角但经常作为“组合拳”的一部分出现。很多快排实现会在递归区间长度小于某个阈值时切到插入排序因为此时数据已经接近有序插入排序的开销比继续递归更小。这是非常经典的生产级优化策略。理解插入排序对读懂这类源码很有帮助。动画化排序算法时建议只对 8 到 15 个元素做演示步间间隔控制在 0.5 秒到 1 秒之间。颜色上可以用灰色表示已排序区红色高亮当前的 key蓝色表示待排序区。这样的视觉层次比所有柱子一种颜色要清楚得多。也可以把每个元素的值标在柱子上方便对照表格理解。13. 总结与下一步插入排序最值得尝试的点是“用手推一遍整个过程”。它没有复杂的数学推导也不需要额外的空间代码写出来只有十几行。第一次上手时先拿[5, 2, 4, 6, 1, 3]这样的数组做动画拆解把每一轮数组状态写出来再对照代码逐行看基本十分钟就能吃透。最先应该验证的是逆序数组和完全有序数组。逆序数组会让插入排序进入最坏情况完全有序数组则会让它进入最好情况两者的比较次数差异非常明显。最容易踩的坑是 while 条件里j 0的顺序以及比较符号写成导致排序不稳定。下一步可以沿着两条线继续深入一条是折半插入排序和希尔排序看如何从“减少移动”和“减少比较”两个方向优化插入排序另一条是学习归并排序和快速排序把它们的时间复杂度 O(n log n) 与插入排序的 O(n²) 放在一起对比会更直观地理解规模化排序为什么需要更高级的算法。排序算法是数据结构的基本功插入排序则是这扇门最好推开的第一扇窗。
