冒泡排序、选择排序、插入排序：O(n²)排序算法原理与优化全解析

先说个结论你要是写了半年业务代码平时大概率不会手动去写这几个O(n^2)排序。但你要是啃数据结构、准备笔试面试这一关绝对绕不开。这是排序系列的开篇我打算从时间复杂度为O(n^2)的三种排序讲起——冒泡排序、选择排序、插入排序。别看它们慢它们反而是理解后续快排、归并排序最好的垫脚石。因为只有把“为什么慢”想透了你才会真正理解那些高级排序到底在解决什么问题。这篇文章的定位很明确不分语言碎碎念直接用可运行的代码和逐步拆解把三种O(n^2)排序的原理、优化、稳定性、应用场景全部讲透。适合把排序背下来但没想明白的人也适合准备笔试时需要快速梳理知识点的同学。1. 先把“O(n²)”这件事看明白1.1 时间复杂度的本质是两个嵌套循环很多人听到“时间复杂度为O(n^2)”就慌其实它没有多神秘。它指的是当输入数据量n翻倍时算法处理这些数据所花的时间会变成原来的4倍左右。为什么是4倍因为O(n^2)意味着运算次数大致等于某个常数乘以n的平方。n从1000变成2000n的平方从100万变成400万那耗时就跟涨到4倍水平。具体到后面这三种排序它们都有一个共同特征程序里必然出现一个外层循环嵌套一个内层循环。外层循环一般用来控制“处理了几轮”内层循环用来“在剩下的数据里做比较或移动”。循环套循环次数就蹭蹭涨。这是判断“这玩意是不是O(n^2)”最直观的方式不用背公式看结构就知道。1.2 为什么先从最“笨”的排序讲起我见过不少学习者直接跳过O(n^2)一上来就啃快速排序、堆排序结果越学越糊涂。原因很简单高级排序里到处都是“分治”“递归”“基准元素”这些概念但它们的底层比较逻辑依然很朴素。如果你连“一个数组处于有序状态时应该怎么检测”这样的判断都写不利索后面很难调试递归到底哪里出了问题。另一个原因是工程里的实际情况O(n^2)排序不总是废柴。当数据量小到一定程度时它们简单、稳定、常数项低很多标准库的混合排序算法甚至会自动切回插入排序。也就是说这不是一段只活在考试里的过期知识。2. 冒泡排序最直观也最容易踩边界坑2.1 最朴素的实现先保证能跑冒泡排序的思路一句话就能讲完每一轮从头到尾把相邻的两个数比较一遍如果顺序反了就交换这样每一轮结束最大的数就会像气泡一样“浮”到最后面。我第一次看这个算法的时候觉得太符合直觉了但当自己动手写仍会在第二个循环的边界上写错。先看最简单的版本def bubble_sort(arr): n len(arr) for i in range(n - 1): # 每一轮都从0开始比较到n-1-i为止 for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j]解释一下为什么内层循环的上限是n - 1 - i。第一轮结束后最大的数已经在数组最后下一轮就不需要再碰它第二轮结束后第二大的数已经在倒数第二位置以此类推。外层循环只需要跑n - 1轮因为最后剩下的一个元素不需要再和别人比较。这段代码虽然能跑但有个问题如果数组本来就已经有序它依然会傻乎乎地比较完所有组合。这就是原始冒泡排序的弊端——它不检查“这轮有没有发生交换”。2.2 优化一提前终止省掉无效轮次优化思路很直接如果某一轮从头到尾一个交换都没发生说明数组已经有序剩下的比较全是白费功夫。加一个标记变量随时准备退出def bubble_sort_with_flag(arr): n len(arr) for i in range(n - 1): swapped False for j in range(n - 1 - i): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True if not swapped: break # 每轮结束时最右端的元素已经就位加了swapped标记之后最好情况下的时间复杂度直接降为O(n)因为第一轮扫描一遍发现没有交换就退出了。对于一个近乎有序的数组工程里经常出现这个优化实际提升非常明显。2.3 优化二记录最后交换位置缩小扫描范围我在实测时发现单纯用swapped标记其实还浪费了很多比较。举一个比较极端的例子数组的后半段已经完全有序只有前半段乱序。这时每次内层循环都会扫描到n - 1 - i但是后半段其实早就该不碰了。更好的做法是记录这一轮最后一次发生交换的位置。最后一次交换的后面所有元素都已经有序下一轮最多扫描到这里就够了def bubble_sort_better_bound(arr): n len(arr) while n 1: last_swap 0 for j in range(0, n - 1): if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] last_swap j 1 n last_swap这个版本把内层循环的上限从固定值改成了动态值。每轮结束后n变成最后一次交换的位置后半段有序区域直接被跳过。数据越接近有序它的轮数就越少整体耗时越接近O(n)。2.4 冒泡排序的稳定性和原地性冒泡排序是稳定排序。所谓稳定指的是如果两个元素的值相等那它们在排序前后的相对顺序不会改变。怎么判断稳定性看交换条件if arr[j] arr[j 1]只有严格大于才交换等于时不动。这一点在面试里经常被单独拿出来问别答错。同时冒泡是原地排序只需要一个临时变量来做交换额外空间复杂度O(1)。这两条都让它成为“教学素材”里最标准的存在。但实际业务里它的性能太差大型项目基本不会用它做主排序算法它更多的是拿来理解“交换排序”思想。3. 选择排序交换次数少但这掩盖不了它的问题3.1 原理和基础实现选择排序的思路和冒泡不同它每一轮只做一次“定位”找到待排序区间里最小的那一个然后把它放到正确位置。比如第一轮找到全数组最小的元素放到第0位第二轮从剩下的里面找最小的放到第1位。它的交换次数是固定的n - 1次在这个点上比冒泡好很多。看代码def selection_sort(arr): n len(arr) for i in range(n - 1): min_idx i for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j if min_idx ! i: arr[i], arr[min_idx] arr[min_idx], arr[i]这里内层循环的作用是“查找最小值的下标”而不是“交换”。查找结束之后最后才做一次交换。我见过不少初学者把min_idx写成arr[i]然后去比大小结果改乱了数据。记住存下标别存值。存值的话最后你还要反向查下标多此一举还容易出错。3.2 为什么它是“不稳定”的选择排序的不稳定经常让人困惑。我就用实际例子说明。假设数组是[3a, 3b, 1]其中3a和3b是两个相等的数字为了区分它们的大小关系用a和b标记。第一轮找到最小值1把1和下标0处的3a交换数组变成[1, 3b, 3a]。原来的3a在3b前面排序之后反而跑到3b后面去了。这就是不稳定。冒泡排序的相邻交换不会产生这种跨距离的移动所以它是稳定的选择排序是“远距离交换”很容易打乱相同元素的相对顺序。如果面试官问你“为什么不稳定”别只答结果要能说出这个例子。这说明你理解的是机制不是背结论。3.3 一个常见误区选择排序一定比冒泡快还真不一定。选择排序的交换次数少但它的比较次数依然是固定的n(n-1)/2和冒泡的最坏情况一样。现在的CPU做一次比较和做一次交换的成本差距不像以前那么大内存缓存的影响甚至更明显。我实测过一组一万条随机整数选择排序和优化后的冒泡排序耗时并没有出现明显差距。原因是优化后的冒泡有提前退出机制数据稍微有序一点就能少跑几轮而选择排序不管数据有序无序每次都要扫描完剩余区间才能确定最小值。换句话说选择排序“太犟了”连最好情况都没有任何减负。3.4 适用场景交换成本比比较成本高得多选择排序唯一的优势场景是交换操作的代价非常昂贵而比较操作相对便宜。比如你要排序的对象是大型结构体移动它需要拷贝大量内存这时选择排序固定n - 1次交换就有价值了。但这种事在业务代码里也不常见你大概率会通过排序索引来解决而不是真的去搬动结构体本身。4. 插入排序扑克牌式思路小数据量的主角4.1 思路与代码实现插入排序的思路特别生活化你打扑克牌摸牌的时候新摸到一张牌会把它插到手里已经排好序的牌堆中合适的位置。数组排序同样如此把数组前面的一部分看成已排好序的区间然后不断把后面的元素往这个区间里插。实现时“插入”不是直接交换而是一个右移的过程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 # 把key放到正确的位置很多人刚看这段代码会懵尤其在arr[j 1] arr[j]这一行。它不是在交换而是在把某个元素向后挪一个位置。因为前面已经有序如果发现前一个数比key大那就说明key应该待在这个数的前面于是这个数先往后退一位给key腾地方。一直挪到某个位置的元素比key小或者到达边界再把key放进去。这个过程里比较是while j 0 and arr[j] key也就是只要前面的数比我大就一直后移。相等时不会移动因此插入排序是稳定性很好的排序。4.2 最好、最坏、平均情况分析插入排序最好情况是数组已经有序。这时内层的while条件一次都不满足每个新元素直接放在原位所以整体时间复杂度为O(n)。最坏情况是数组逆序比如[5,4,3,2,1]。每次插入都要把前面所有的元素往后挪一次比较和移动次数都达到最大值整体复杂度O(n^2)。平均情况还是O(n^2)。但注意这里有个关键差异插入排序的“常数项”通常比其他O(n^2)排序低。因为它的比较和移动大多发生在内存中很近的区域缓存友好度很高。同样是O(n^2)实际跑起来它往往快于冒泡也快于选择排序的很多场合。4.3 两个实用变种二分插入排序和“区间半开”思想二分插入排序是在找插入位置时不一个一个比较而是用二分查找把比较次数从O(n)降到O(log n)。不过注意数组元素的移动次数依然是O(n)所以整体时间复杂度并没有变成O(nlogn)。它的实际收益是减少了一半左右的比较开销对数据量大一点的场景能感觉到速度变化。还有一种工程上更常见的变种“把数组先按步长分组做插入排序”这就是希尔排序的前身。严格算起来希尔排序的复杂度已经不完全是O(n^2)所以等后面我写进阶篇时再展开讲。这里提它是想让你把插入排序理解为一个“骨架”后续很多优化的底层逻辑都建立在它之上。4.4 插入排序和冒泡、选择的最大区别同样是比较加移动插入排序最强的点是“局部性”。它处理新元素时只用看当前元素前面的小区间而且这个区间基本上是有序的。数据一旦近乎有序它的优势立刻被放大。这让我想起很多工程师拿到的“时间戳列表”排序。真实业务里的日志、订单时间序列经常是“接近有序”的这时候插入排序的实际表现能接近O(n)而快排在这类数据上反而可能不平衡。5. 把它们摆在一起性能对比、稳定性、适用场景5.1 三张表看清区别排序算法最好情况平均情况最坏情况额外空间稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定排序算法比较次数交换/移动次数主要特点冒泡排序较多但可以提前退出最多n(n-1)/2次交换容易理解稳定性好性能一般选择排序恒定n(n-1)/2次最多n-1次交换交换次数少不稳定无提前退出插入排序数据越有序越少移动次数依赖逆序程度对“接近有序”数据接近O(n)缓存友好使用场景推荐选择手写简单排序、教学演示冒泡排序数据量很小少于几百条插入排序更稳交换成本极高要求交换次数最少选择排序近乎有序的数据插入排序尽量别选快排5.2 常数项和内存局部性比复杂度更影响实际体感我见过有人只知道看大O看到三个排序都是O(n^2)就认为性能差不多这是大错。大O描述的是“增长趋势”但实际运行时还有常数项、内存缓存命中率、分支预测等等。插入排序之所以在这三个里往往最实用就因为它内部循环非常紧凑访问的地址基本挨在一起CPU缓存命中率高。冒泡排序虽然代码也简单但它的交换操作比插入排序的移动操作要重多了一次读和两三次写。选择排序则是每次都要遍历很长的剩余区间缓存命中率也一般。所以如果现在你手头有一个几百条数据的小列表需要排序我的建议是先写插入排序别动不动就引一个复杂排序。实测下来插入排序在几百条数据这个量级和快排差距极小而且代码不容易出错稳定性和可读性都更好。5.3 工程标准库里为什么经常“混合排序”很多主流语言的排序库并不只用一种算法。它们会在递归到比较小的子数组时自动切换到插入排序。这不是因为快排在小数组上更慢而是因为递归本身有函数调用开销当子问题太小时这种开销反而超过排序本身。所以在工程世界里O(n^2)排序不仅不是“僵尸代码”反而是一种重要的补充策略。这也是我说不要把学习重点完全放在“造火箭”上的原因。掌握插入排序你以后看混合排序的源码时会很容易理解它为什么要做这种切换。6. 面试和上机中常见的坑以及我自己的排查经验6.1 边界条件清单动手前先确认写排序最容易翻车的不是算法逻辑而是边界。我列一个我常用的自检清单数组长度为0或长度为1循环是否直接不进入range(n - 1)的写法在n0时是否会直接跳过冒泡的内层j的最大值是否可能越界访问arr[j1]插入排序的j - 1之后是否可能变成-1元素全相等时算法能否正常退出其中冒泡排序里最容易出现arr[j1]下标越界的问题。我第一次手写时就因为把上限写成了range(n)导致最后一轮访问了不存在的元素。解决办法很简单内层上限是n - 1 - i不是n - i。如果心里没底先用小数组手动模拟一轮。6.2 一个隐蔽的问题swap写错导致数据丢失Python里arr[i], arr[j] arr[j], arr[i]很方便但在手写交换逻辑时我见过不少人写成arr[i] arr[j] arr[j] arr[i]这样根本不会交换因为第二行执行时arr[i]已经被覆盖了导致两个位置变成同一个值数据直接丢失。正确写法是引入临时变量tmp arr[i] arr[i] arr[j] arr[j] tmp这个错误在C/C或者Java里尤其常见。如果排序结果里莫名出现很多重复值第一件事就去检查交换逻辑。6.3 如何判断自己有没有优化到位我自己的做法是先写一个生成大量随机数的脚本分别测原始版和优化版的耗时。比如一万条数据冒泡排序的原始版明显更慢加了提前退出后如果生成的数据接近有序速度差距能拉到两倍以上。插入排序则是直接随机数、升序、降序三组数据都要测用来验证O(n)、O(n^2)的差异。如果面试现场不能跑代码就手动模拟一轮。用[5, 1, 4, 2, 8]这种长度5的数组每轮循环后把数组状态写下来自己能讲清楚每一轮的变化基本就是真的理解了而不是背代码。6.4 实战选择建议什么时候真的该用它们如果有一段业务代码要处理几百条数据我不建议为了“显得高级”硬套快排。直接用插入排序或者用语言内置排序代码更清晰也少很多边界问题。如果数据规模上千但接近有序插入排序优先。如果是几万条以上乱序数据那就别用这三种了交给归并或快排。同时记住语言内置的排序往往已经做了混合优化实际性能远超过你手写的快排。写手写排序主要为了笔试和面试业务代码里能用内置函数就不要重复造轮子。7. 把这个系列往下顺延我先说点学习上的建议我建议你看完这篇文章后不要急着背下一部分的内容先把冒泡、选择、插入三种排序分别手写三遍写到不需要思考就能避开所有边界错误为止。排序算法这块最怕眼高手低。我自己当年踩过的坑包括下标越界、交换写错、优化标记忘记重置全都在笔试现场犯过。后来老老实实把每个排序的“手动模拟一轮”练熟才算真正过关。下一篇我会开始讲O(nlogn)级别的排序重点拆解快速排序和归并排序的分治思想以及为什么它们能突破O(n^2)的天花板。但突破归突破你依然是先把这篇的基础打牢再说不然递归里的基准元素选谁、怎么切分你都会觉得很抽象。