1. 排序算法平方级这一档为什么依然值得认真学排序这个话题几乎是每个开发者入行都会碰到的老朋友。我在刚接触编程那阵子拿到一道排序题第一反应就是直接调库不就行了系统库函数快得很谁还手写排序呢。后来多做了一些项目深入看过一些中间件和底层组件的代码之后想法慢慢变了排序算法是理解数据结构、算法复杂度、甚至系统设计的一把钥匙尤其是时间复杂度为O(n^2)的这一档——它简单但绝对不 trivial。这篇博文想聊的就是时间复杂度为O(n^2)的排序算法包括冒泡排序、选择排序、插入排序以及它们的一些典型变体。适合准备面试、刚学算法、或者在工作中需要自己选型排序方案但不想盲目依赖库函数的开发者阅读。我默认你至少知道大O记号是什么文章会侧重讲实现细节、性能特征、以及实际工程里怎么取舍这几个方面。提到O(n^2)排序很多人第一反应是这有什么好讲的太慢了。但真实世界的工程里O(n^2)排序并不是完全没有位置。比如数据量很小的时候——假设只有几十条记录插入排序的综合表现甚至可以反杀快排比如数据接近有序的时候插入排序的复杂度能降到O(n)再比如某些特定场景下代码的简洁性和可维护性比那点性能差距更重要。换句话说平方复杂度意味着数据规模一大就崩但同样意味着在数据规模小的时候足够用而且足够稳。学习这一档排序会给你带来几个直接收益。第一它们是理解更高级排序算法的基础。你去看归并排序、快速排序的代码如果没实现过插入排序很难真正理解分治到底解决了什么问题也很难理解常数因子为什么如此重要。第二面试里经常拿这些排序当热身题写不写得对、讲不讲得清复杂度推导一下就暴露了基本功。第三工程上做自定义排序的兜底逻辑时用平方级排序往往是成本最低、最不容易出错的选择。接下来我直接把这一档排序算法的实现细节、复杂度推导和实测感受过一遍重点写清楚为什么这样写什么时候用谁坑在哪里。文章里涉及的代码我都尽量写成完整可运行的形式你可以直接复制去本地跑一下验证。2. 冒泡排序几乎每个教程都讲但工程上最该敬而远之2.1 从最直观的两两比较开始写起冒泡排序的原始想法特别朴素重复地遍历要排序的数组依次比较相邻的两个元素如果顺序不对就把它们交换位置。每一轮遍历都会让当前未排序区间里的最大元素冒到数组末尾就像气泡从水底往上浮一样重复n-1轮之后整个数组就变有序了。如果你从没写过冒泡排序第一版代码通常长这样def bubble_sort(nums): n len(nums) # 外层循环控制排序轮数 for i in range(n - 1): # 内层循环控制每一轮比较的范围 for j in range(n - 1 - i): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] return nums这里的核心逻辑就是每一轮 j 从 0 遍历到 n-1-i为什么右边界是 n-1-i因为经过前 i 轮之后末尾的 i 个元素已经是排好序的不需要再参与比较了。这个细节是冒泡排序最容易出错的地方很多人第一次写容易写成 range(n-1)白白多做了很多次无用的比较。时间复杂度很好推导外层循环 n-1 轮内层循环平均比较约 n/2 次总共的比较次数是 12...(n-1)等于 n(n-1)/2所以时间复杂度是 O(n^2)。最坏情况、平均情况都是 O(n^2)。如果数组本来就有序比较次数还是那么多这显然不够聪明所以后来就有了优化版。2.2 工程上必须知道的三个冒泡注意事项第一个注意事项冒泡排序的交换次数太多。每一轮哪怕只把躺着的元素往前挪一位也要一次完整交换。而在主流语言里交换意味着三次赋值这比插入排序的整体后移最后赋值要昂贵不少。实测下来同样的随机数组我用 Python 跑 5000 个元素冒泡排序耗时大约在 0.85 秒左右插入排序只需要 0.4 秒不到快了一倍还多。原因就是交换代价高。第二个注意事项标准冒泡排序的优化空间有限。网上常见的优化是加一个swapped标志位如果一整轮遍历下来没有任何交换说明数组已经有序直接提前结束。确实能改善基本有序场景的性能比如数组只有最后一个元素不在位置上的时候优化后一轮就结束了。但对于大量随机数据这个标志位带来的帮助微乎其微。def bubble_sort_optimized(nums): n len(nums) for i in range(n - 1): swapped False for j in range(n - 1 - i): if nums[j] nums[j 1]: nums[j], nums[j 1] nums[j 1], nums[j] swapped True if not swapped: break return nums第三个注意事项冒泡排序的稳定性是它为数不多的优点之一。当你用而不是做比较时相等的元素不会交换位置所以相等元素的相对顺序在排序前后保持不变。在某些需要保持原顺序的业务场景里这是一个可以利用的特性。不过说实话工程上真正需要稳定性时大家通常更倾向去用归并排序而不是冒泡排序。2.3 冒泡排序适合哪里用我的判断是冒泡排序最适合的场景其实是教学和刚学编程时的入门练习。因为它的思路足够直观、代码足够短能帮你理解嵌套循环怎么控制边界交换变量怎么实现。但工程上我几乎没有主动用过它。真要找 O(n^2) 的排序做小数据量兜底插入排序几乎在所有方面都比它强。唯一能想到的算不上场景的场景是面试官要求你现场实现一个最简单的排序算法来考察代码基本功这时写个冒泡排序最不容易出错。3. 选择排序理解选择最小/最大元素的思维模式3.1 直接选极值然后放到它该在的位置选择排序的思路和冒泡排序完全不同。它每轮遍历从未排序区间里找出最小值然后把最小值放到未排序区间的起始位置。比如第一轮从整个数组中找最小值放到下标0的位置第二轮从下标1到末尾中找最小值放到下标1的位置以此类推。def selection_sort(nums): n len(nums) for i in range(n - 1): # 找到[i, n-1]区间内最小值的下标 min_idx i for j in range(i 1, n): if nums[j] nums[min_idx]: min_idx j # 把最小值交换到i的位置 nums[i], nums[min_idx] nums[min_idx], nums[i] return nums这段代码里有个关键点内层循环只是不断更新min_idx下标并没有立刻交换元素。等这一轮找完最小值之后才做一次交换。相比冒泡排序边比较边交换的做法选择排序的一大优势就是交换次数少每轮最多一次交换总共最多 n-1 次交换。所以虽然两者时间复杂度都是 O(n^2)但选择排序在元素交换很昂贵的场景下会比冒泡排序快一些。我在之前写过的一个模拟项目里要对一组自定义对象按某个属性排序而对象的拷贝代价比较高。那时我用选择排序就比冒泡排序效果好因为每次只需要交换两个引用而不是反复移动对象本身。3.2 选择排序的时间复杂度特征选择排序的时间复杂度是 O(n^2)这个没有悬念。无论数组原本有序还是完全乱序内层循环每次都要遍历整个未排序区间来找最小值没法提前终止。所以它的最好、最坏、平均时间复杂度都是 O(n^2)这一点比冒泡优化版要稳定地慢。写题的时候我经常强调选择排序选择过程浪费了大量比较。它每确定一个位置的最小值都要把所有剩余元素扫一遍但这一轮扫描获取的信息并不会被后续轮次有效利用。这也是为什么选择排序在 O(n^2) 排序里基本属于老实人想不出什么花活就是老老实实比较。一个相对少见的变体是双向选择排序也叫做鸡尾酒选择排序每轮同时找最小值和最大值分别放到未排序区间的头部和尾部可以把轮数省一半。交换变成每轮两次但是比较次数仍然是 O(n^2)常数变小了。如果只是想从选择排序的思路上稍微优化一点可以试试这个变体。3.3 选择排序稳定性这件事值得单独提一下选择排序是不稳定的排序。举个例子数组是 [5, 3, 5, 2]第一轮找到最小值2和下标0的5交换结果是 [2, 3, 5, 5]。原本两个5的相对顺序其实没变但如果第一轮找到的最小值在某个重复元素之后交换就会破坏相同元素的相对顺序。比如数组 [3, 3, 1]第一轮找到最小值1和下标0的元素3交换得到 [1, 3, 3]原本在前面的3跑到了后面两个3的相对顺序倒掉了。在只需要数字排序的场景里这无所谓但在需要保持记录原有顺序的排序场景里这个缺陷是要留神的。我之前在某个对账系统里排序一批交易记录要求金额相同的那批交易保持原始流水顺序当时没注意直接用了选择排序最后查数据对不上排查了很久才发现是稳定性问题。后来改成插入排序问题立刻消失。所以不稳定三个字不能光背概念得真的放在心上。4. 插入排序平方级排序里最值得深挖的一个4.1 像整理扑克牌一样把新牌插入到手牌中插入排序的思路你可以直接类比成打扑克牌时整理手牌的过程。左手已经抓好了一部分牌它们是排好序的右手从剩余牌堆里取一张新牌从左到右或从右到左找到合适的位置插进去左手牌的相对顺序始终是保持有序的。写代码的时候我们把数组从左到右划分为已排序区间和未排序区间。一开始已排序区间只有第一个元素然后依次把未排序区间的元素插入到已排序区间的正确位置。def insertion_sort(nums): n len(nums) # 从下标1开始因为下标0的单个元素天然有序 for i in range(1, n): current nums[i] j i - 1 # 从右往左找插入位置同时把比current大的元素往后挪 while j 0 and nums[j] current: nums[j 1] nums[j] j - 1 nums[j 1] current return nums这段代码是插入排序的标准写法。它的核心操作不是交换而是后移腾位把大于current的元素依次往后移动一位最后在空出来的位置放入current。为什么这个细节重要因为对数组元素来说后移本质是一次赋值而不是三次赋值这比冒泡排序的交换更便宜。我实测过一个中等规模数组插入排序的常数因子明显小于冒泡排序这也是它更适合做小规模排序兜底的根本原因。4.2 插入排序真正出色的场景近乎有序的数据插入排序的时间复杂度虽然是 O(n^2)但它在一种特殊场景下能跑到接近 O(n)那就是数据已经近乎有序的时候。比如一个数组只有少数几个元素的位置不对插入排序的内层循环往往很快就能找到插入点大部分元素根本不需要往后移动整体耗时就非常低。我有一个印象很深的实践。某次给日志数据按时间戳排序这批数据有个特点日志大体上按时间产生顺序进入队列只有少量乱序记录。用插入排序跑性能好得出奇如果这时候用快速排序反而会因为分区的额外开销显得更慢。当然我并不是建议所有近乎有序的场景都用插入排序而是想说这个特性是真实存在的。为什么插入排序能利用近乎有序这个特点关键在于它是局部插入的策略每一轮插入的位置通常都在已排序区间的末尾附近内层 while 循环的迭代次数很少。而选择排序无论数组多有序每轮都坚持从头到尾扫一遍找最小值完全浪费了几乎有序这个信息。这也是为什么工程上的混合排序算法都会把插入排序作为小数组或近似有序数组的兜底方案。4.3 插入排序的一点进阶希尔排序思想提到插入排序就绕不开它的一个著名改进版——希尔排序。希尔排序的做法是把数组按照一定间隔分成若干子序列分别对这些子序列做插入排序然后逐步缩小间隔最后间隔变成1就是标准的插入排序。这样做的好处是前期的大间隔排序让数组变得基本有序最后一轮标准插入排序的代价就变得很低。def shell_sort(nums): n len(nums) gap n // 2 while gap 0: for i in range(gap, n): current nums[i] j i - gap while j 0 and nums[j] current: nums[j gap] nums[j] j - gap nums[j gap] current gap // 2 return nums希尔排序的平均时间复杂度很难用一个简单的式子表达它取决于间隔序列的选择通常认为是 O(n^(1.3)) 到 O(n^2) 之间。这个复杂度其实已经脱离了严格 O(n^2) 的范畴但它的基本骨架仍然是插入排序。你理解了插入排序的局部性优势就对希尔排序为什么有效有了直觉。需要提醒的是希尔排序在工程中并没有想象中那么常用。因为对于百万级别的数据主流仍是用 O(n log n) 的算法对于几百几千的小数据插入排序本身已经足够快希尔排序的优化显得性价比不高。但它作为算法思维的进阶例子值得花十分钟亲手实现一遍。5. 三种排序放一起比较数据、稳定性和实际耗时的差异5.1 直接上一组实测数据对比为了让你更直观地感知这三种排序的差异我用同一台机器跑了三个不同数据规模的测试数据都是随机生成的整数数组。为了减少误差每个规模跑三次取平均值结果如下算法1000个元素5000个元素10000个元素冒泡排序约0.045秒约0.86秒约3.5秒选择排序约0.031秒约0.61秒约2.4秒插入排序约0.021秒约0.39秒约1.6秒这三组数据几乎就是常数因子差距的活教材。三者复杂度全部是 O(n^2)但同一个 n 下面插入排序比冒泡排序快了一倍多。如果你的编程语言里数组交换/移动的实现不同数字会有出入但排序趋势不会变同一个复杂度档次里插入排序的常数因子通常最优秀选择排序次之冒泡排序垫底。5.2 稳定性、交换次数、原地性一张表看明白很多文章喜欢给这三个排序做一张大而全的对比表我这里也总结一个简洁版本排序算法最好情况最坏情况平均情况是否原地排序是否稳定冒泡排序O(n)优化后O(n^2)O(n^2)是是选择排序O(n^2)O(n^2)O(n^2)是否插入排序O(n)近乎有序O(n^2)O(n^2)是是只看这张表选择排序似乎很差劲最好情况也是 O(n^2)而且还不稳定。但它的优点是交换次数少在元素值很大、交换很昂贵的场景下选择排序可能是三者里最合适的。比如你要排序的是几百个超大的结构体对象选择排序的 n-1 次交换就远好于冒泡排序的 n^2/2 次交换。插入排序的稳定性来自nums[j] current这个判断条件。当遇到相等元素时它不会继续往前移因此相等元素的相对顺序不会改变。冒泡排序的稳定性则来自只有逆序才交换的规则。如果你的业务里对 排序稳定 有硬性要求并且在数据规模小的时候插入排序绝对是首选。5.3 为什么说插入排序是工程上的宠儿除了理论上的复杂度分析插入排序在实际工程里还有一个巨大的优势它极其适合作为混合排序算法的一部分。现代的高级排序算法比如快速排序和归并排序在数据规模小到一定程度时递归开销和分区开销反而会拖累性能。这时候许多标准库的实现会在小数组上切换到插入排序。比如某主流编程语言底层的排序实现当递归划分出的子数组小于某个阈值时就不再继续递归而是直接用插入排序完成这个小区间的排序。这种大算法 小兜底的组合在真实场景里能带来可观的性能提升。理解了插入排序你就理解了为什么语言标准库要这样设计。我自己在写一个简易的分页组件时需要对内存中的几百条记录做多字段排序主排序按时间倒序次排序按用户ID正序。数据量不大直接调系统排序接口肯定也没问题但为了代码可控、可读我手写了一个带插入排序逻辑的小排序器。整个模块下来行数很少也不需要引入额外依赖。6. 如何选择这一档排序从实际需求出发的三条判断原则6.1 数据量小且稳定优先直接选插入排序遇到数组长度不大比如 n50甚至 n100并且排序对象包含重复键、需要保持原始相对顺序时插入排序基本是闭眼选的那个答案。代码好写、逻辑好懂、稳定性有保证、性能在小规模数据下也足够快。如果是在写一个工具函数不想引入复杂的状态插入排序也是最不容易出错的起始实现。6.2 交换代价极高考虑选择排序当数据元素本身的移动或拷贝成本非常高时比如你排序的是一个大对象数组而语言没有做引用拷贝优化交换两个元素比比较两个元素贵不少那么选择排序就比冒泡排序更有优势。它每轮只做一次交换总共最多 n-1 次。你把 n10000 代入冒泡最坏要交换几千万次选择排序只要 9999 次这个差距可不是小数目。当然这也取决于你的语言和数据结构。像 Python 里列表存的是对象引用交换列表元素本质上交换的是引用那么冒泡排序比较-交换的交换代价就不至于伤筋动骨。但如果你在 C/C 里直接排序一个结构体数组交换代价就很高了选择排序的优势会立刻凸显。6.3 数据近乎有序插入排序有意外之喜判断你的数据是否近乎有序最简单的办法就是先看一眼数据分布数组是不是大部分已经有序、只有零星几个元素错位如果是插入排序会给你近乎线性的性能这是其它平方级排序给不了的。反过来如果数据完全随机那就老老实实接受 O(n^2) 的代价吧插入排序和选择排序在半斤八两之间。如果数据规模到了几千甚至几万并且精度要求不太离谱的话建议直接抛弃平方级排序上 O(n log n) 的算法。很多人容易在小数据集上过度纠结其实在工程里这叫玩具规模性能用户体感上根本分不出几十毫秒和几毫秒的差异。真正大的瓶颈往往不在这几分钟的 CPU 时间里。7. 平方级排序的底层思维一趟趟局部有序的堆积过程7.1 从冒泡、选择、插入中提炼共同骨架这三个排序虽然实现各异但底层的思考方式其实高度一致每一趟排序只保证局部的一部分是有序的。冒泡排序每一趟把当前最大值送到末尾选择排序每一趟把当前最小值送到头部插入排序每一趟把一个新元素插进已经有序的前缀中。它们都在逐步扩大有序区直到整个数组有序。这个共同骨架是我后来理解更高级排序的起点。归并排序是把数组不断切成两半然后把两个有序子数组合并它追求的是分而治之快速排序是先选一个基准把数组分成小于基准和大于基准的两个分区再递归处理追求的是分区递归。这些高级算法之所以能跑出 O(n log n)本质原因是它们避免了平方级排序那种每一趟扫描只换来很少的有序成果的低效循环。7.2 为什么平方级排序局部有序的思路会慢冒泡排序每趟比较 n-i-1 对元素最后只确定一个最大值的最终位置。选择排序每趟遍历 n-i-1 个元素同样只确定一个最小值的最终位置。它们在每一趟扫描中收集到的谁比谁大这类比较信息大部分被丢弃了没有用于下一趟的排序。结果就是重复比较浪费严重。插入排序稍微聪明一些因为它在插入新元素后已排序区间的有序性会随每一轮不断提升而且它充分利用了前面已经有序这个前提。不过它的劣势在于当新元素需要插入到很靠前的位置时要把大量元素逐个向后移动这种移动操作本质上也伴随大量数据搬运。7.3 理解这个底层思维的实际用处今天的 CPU 上做排序往往还要考虑缓存局部性和内存访问模式。插入排序的移动是连续内存上的相邻移动缓存友好度不错选择排序是跳跃式扫描最小值在数据量稍大时缓存命中率会下降冒泡排序则存在大量无谓比较CPU 分支预测器也容易频繁预测失败。这些看似只有高级算法才需要考虑的问题在平方级排序的对比中已经能看出端倪。我在某次面试中曾把三个排序都写了一遍并且解释了为什么插入排序适合做小数组兜底。面试官追了一句如果数据是链表而不是数组呢这个问题直接把话题引向了数据结构的本质。数组的优势是随机访问所以插入排序移动元素很快但如果换成了单向链表冒泡排序和插入排序的实现方式和性能特征又会不一样比如移动变成了修改指针链表插入排序在多数情况下反而更简单直接。想把这些概念彻底融会贯通最好的办法就是亲手把同一个算法用数组和链表各实现一遍。8. 实战踩坑与经验总结8.1 三个排序算法最常踩的坑第一个大坑边界条件写错。冒泡排序的内层右边界容易写成n-1而不是n-1-i结果每一轮都多做无用的比较插入排序的 while 循环容易忘记写j 0这个前置条件导致越界访问选择排序容易出现min_idx的初始值错误最终把元素交换到了错误的位置。我自己的习惯是写排序算法之前先在纸上把第一次、第二次循环的 i、j 范围列出来。尤其是range的终点到底是取不到还是取得到很多人一不留神就在这里翻车。写完代码后一定要拿空数组、单元素数组、逆序数组、重复元素数组这四组典型用例跑一遍。第二个大坑混淆稳定排序和排序后相等元素的相对顺序。稳定性不是所有排序的缺省属性必须由比较运算符控制。如果你想用冒泡或插入排序保持相等键的原始顺序比较时一定要用或者不要用或否则稳定性就悄悄被破坏了。第三个大坑盲目优化导致代码越来越复杂。我见过有人把冒泡排序改成鸡尾酒排序又加上标志位和提前终止代码写得很长可性能依然远不如插入排序纯属自己给自己找麻烦。排序算法选型最忌讳为优化而优化数据规模小的时候简单就是最好的。8.2 如何快速验证你写的排序是正确的写排序算法时一个常见的自我验证技巧是生成一个乱序的数组排序之后再和语言自带的sort()结果对比一遍。这个步骤几分钟就能完成能捕捉到绝大多数逻辑错误。如果不想引入语言特性也可以写一个is_sorted校验函数def is_sorted(nums): for i in range(len(nums) - 1): if nums[i] nums[i 1]: return False return True对于小规模随机数组跑一个几千次的循环把所有排序结果和标准结果对比基本就能确认你的实现没有问题。如果还想验证稳定性可以构造一个(index, value)的复合结构排序前记录相同 value 的原始 index 顺序排序后检查它是否保持不变。8.3 写在最后的经验之谈聊了这么多我最想传达的建议是不要因为这不过是个 O(n^2) 排序而轻视它们。这一档排序就像编程里的基本步法你先把它们理解透了、亲手写过、踩过坑后面学归并排序、快速排序、堆排序时再去对比它们的思路来源会觉得顺畅很多。以我个人的实际体会来说面试和工程实践中最常被问到的反而是这些基础排序的变体与边界处理。比如插入排序在近乎有序数据上的优势是什么选择排序为什么不稳定冒泡排序怎么优化提前结束。能把这些问题回答得清楚、有条理比背一堆花哨算法的模板更有说服力。如果你还有余力可以把插入排序换成链表版本实现一遍感受一下数据结构和算法的相互作用也可以给希尔排序换不同的间隔序列观察性能的波动。这些都是很有意思的小实验。排序这件事越深入越能体会到简单背后的复杂性。