如果你在大学或者自学阶段学过数据结构多半已经把冒泡、选择、插入这三种排序背得滚瓜烂熟冒泡就是两层循环选择就是每次找最小插入就是像打扑克牌。但真被问到“为什么冒泡排序的交换次数恰好等于逆序对数量”“为什么选择排序不稳定”“为什么插入排序在近乎有序的数据上能跑出接近 O(n)”很多人会卡壳。这不丢人因为大多数资料只教了怎么写代码没讲清楚代码背后到底在做什么。这篇文章把六大经典排序的底层逻辑拆开聊一聊。既然是上篇先把最基础也最容易让人轻视的三兄弟讲透冒泡排序、选择排序、插入排序。下篇再聊希尔、归并和快排。如果你能把这几个问题想明白后面看高级排序会轻松很多。1. 排序的底层共同语言逆序对、稳定性与自适应1.1 逆序对藏在一组数据背后的“混乱总量”先别急着背复杂度先把“逆序对”这个概念吃透。定义很简单对于数组中的两个位置i j如果arr[i] arr[j]那(arr[i], arr[j])就是一个逆序对。比如数组[3, 1, 2]里(3,1) 和 (3,2) 是逆序对总共 2 个而[1, 2, 3]一个都没有。逆序对数量可以理解为“这组数据离完全有序还有多远”。排序算法本质上要做的事就是把所有逆序对消除掉。不同算法的差异只是消除逆序对的方式不一样冒泡通过相邻交换一次消灭一个插入通过把元素往前搬动一次消灭若干个选择则是在每一轮里定位一个最小值把它放到正确位置从而慢慢压缩剩余逆序对。这个视角非常有用。后面分析复杂度时你会发现很多排序算法的实际耗时并不是固定的O(n²)而是和逆序对数量密切相关。数据越接近有序逆序对越少某些算法就越省力。1.2 稳定性当相等元素也要讲先后顺序稳定性说的是如果数组里有两个值相等的元素排序后它们的相对顺序会不会改变。不改变就是稳定排序改变了就是不稳定排序。有人可能会问值都相等了顺序还重要吗在只按单一数字排序时确实无所谓但在真实业务里排序往往是“多字段”的。比如先按班级排序再按成绩排序。如果第二次排序是稳定的那每个班级内部仍然保持着第一次排好的成绩顺序如果第二次排序不稳定班级内部成绩顺序可能被打乱。所以稳定性不是理论洁癖而是工程里实实在在的需求。冒泡和插入天然稳定选择天然不稳定这一点在选择排序的章节里展开讲。1.3 自适应能力算法对输入顺序的敏感度“自适应”是另一个容易被忽略的概念。如果算法的耗时明显依赖输入数据原本的有序程度那它就是自适应的。反过来无论输入是升序、降序还是乱序耗时都一样那就没有自适应能力。最典型的是插入排序数据已经有序时它几乎只需扫描一遍数据完全逆序时它才进入最坏情况。冒泡排序加上提前终止标记后也是自适应的。选择排序不是因为它每一轮都必须扫完剩余区间才能确定最小值初始顺序帮不上一点忙。有了逆序对、稳定性、自适应这三个坐标接下来的三个算法就不再是孤立的代码片段而是三种不同的“消除混乱”策略。2. 冒泡排序相邻交换为什么交换次数等于逆序对数2.1 一趟遍历最大值如何一步步浮到末尾冒泡排序的直观描述是每一轮从头到尾比较相邻的两个元素如果前一个比后一个大就交换。这样每一轮结束后当前未排序区间里的最大值一定会被“推”到末尾。为什么最大值一定归位因为它只要遇到比自己小的相邻元素就会被换到右边就算它前面有几个更大的那些更大的会先被交换到它后面最终最大值也会一路向右走到终点。换句话说每一轮等价于“把当前未排序区间的最大值冒到最右端”。用 Python 写一个优化过的冒泡排序def bubble_sort(nums): nums nums[:] n len(nums) boundary n - 1 while boundary 0: last_swap 0 for i in range(boundary): if nums[i] nums[i 1]: nums[i], nums[i 1] nums[i 1], nums[i] last_swap i boundary last_swap return nums这里先不做优化只看基本思想每一轮比较相邻元素把大的往后移。最外层循环最多跑n - 1轮因为最后剩下一个元素时不需要再排。2.2 相邻交换一次正好消灭一个逆序对这是冒泡排序最容易被忽略的底层逻辑。交换两个相邻元素nums[i] nums[i1]只会改变这两个元素之间的相对顺序而且交换后逆序对被消灭了。值得注意的是这次交换不会影响这两个元素和区间外其他元素的逆序关系所以全局逆序对数量正好减一。因此冒泡排序的总交换次数严格等于初始数组的逆序对数量。比如[4, 3, 2, 1]有 6 个逆序对完整跑完冒泡交换次数也正好是 6。这一点和“相邻交换只能逐个消除逆序对”直接对应。这个理解有什么用它能解释为什么冒泡排序在接近有序的数组上很快。如果数组只有一个逆序对比如[1, 2, 3, 5, 4]冒泡一趟可能就发现没有交换了直接结束。但如果数组完全逆序逆序对数量是n(n-1)/2冒泡就会老老实实交换那么多次复杂度自然到了O(n²)。2.3 提前终止与有序边界优化很多教学代码里冒泡是这么写的for i in range(n - 1): for j in range(n - 1 - i): if nums[j] nums[j 1]: swap它有个问题即使某轮已经完全没有交换算法仍然要继续往后跑完所有轮次。给内层循环加一个swapped标记可以在某轮无交换时直接终止。这是“提前终止”优化。另一个优化是“记录最后交换位置”。每轮内层循环中最后一次发生交换的位置之后所有元素都已经有序。下一轮完全没有必要再遍历到整个数组末尾只要遍历到last_swap就行。上面的boundary版本就同时包含了这两个思想。这两种优化在随机数组上不会改变复杂度量级但在“前面乱、后面有序”的数据上收益明显。比如数组[3, 1, 2, 4, 5, 6, 7]第一轮后[1, 2, 3, 4, 5, 6, 7]最后交换位置在索引 1下一轮只需要比较前两个元素耗时很小。2.4 复杂度、稳定性与真实位置冒泡排序最好情况是O(n)也就是数组已经有序且带提前终止标记最坏和平均都是O(n²)。它稳定因为只有当时才交换相等元素不会越过彼此。空间复杂度是O(1)是原地排序。工程上纯冒泡排序很少被直接使用因为插入排序在同样稳定的前提下常数因子更小、移动方式更高效。但冒泡排序的教学价值极高它将“相邻交换消除逆序对”的思想展示得最直观也是理解后面归并排序“合并有序区间”时的反面参照。3. 选择排序比较恒定的一根筋交换次数最小化3.1 每次挑“最小”比较次数却雷打不动选择排序的思路非常直接第一轮扫描整个数组找到最小值放到第一个位置第二轮扫描剩余部分找到最小值放到第二个位置依此类推。def selection_sort(nums): nums nums[:] n len(nums) for i in range(n - 1): min_index i for j in range(i 1, n): if nums[j] nums[min_index]: min_index j if min_index ! i: nums[i], nums[min_index] nums[min_index], nums[i] return nums关键点在于不管输入数据原本有多有序选择排序每一轮都必须完整扫描剩余未排序区间才能确定最小值。第一轮要比较n-1次第二轮n-2次直到最后一轮比较 1 次总比较次数固定为n(n-1)/2。这意味着选择排序完全没有自适应能力。即使输入已经升序排列它也要做同样多的比较。它唯一能省的是交换次数每一轮最多只交换一次总共最多n-1次。3.2 为什么选择排序是稳定的反面教材选择排序不稳定这个结论几乎所有教材都直接给出但很少解释清楚。来看一个例子数组[5a, 5b, 3]其中5a和5b是两个值相同的元素只是为了区分来源。第一轮扫描找到最小值 3它的位置在索引 2。算法会拿它和索引 0 的5a交换数组变成[3, 5b, 5a]。此时两个 5 的相对顺序从5a - 5b变成了5b - 5a稳定性被破坏了。问题出在哪选择排序为了把最小值放到最前面会把原位置上的元素直接换到后面而这个“被换走”的元素可能恰好是某个相等值的更早版本。只要在普通数组上采用“交换”而不是“搬移”就很难同时做到最少的交换次数和稳定性。如果强行让它稳定比如不用交换而用类似插入的搬移方式那么每一轮都可能移动多个元素时间复杂度不变但常数增大而且算法已经不再是“每轮最小交换”的模型了。工程上如果既想要 O(n²) 又想要稳定直接用插入排序更划算。3.3 交换次数最少的 O(n²)适合写多读少场景选择排序的最大价值在于交换次数少。在数组元素是非常大的结构体、或底层写入成本很高时减少交换次数可能比减少比较次数更重要。比如你在嵌入式环境里维护一个对象数组交换两个对象需要拷贝整块内存而比较两个对象的 key 只是读几个字段。这时选择排序的“比较多、交换少”就有实际意义。它最多做n-1次交换不会因为数据本身乱序而增加交换次数这一点在写入成本敏感的场景中很耐打。当然如果比较成本本身也高比如两个“大小”需要通过复杂的评分函数计算那选择排序的海量比较就成了缺点。没有万能算法只有结合数据特征和硬件成本后的取舍。3.4 选择排序给人的一句实在话如果你面试时被问到“选择排序有什么优点”别只说“简单”。真正能加分的回答是它的比较次数与输入顺序无关交换次数恒定为O(n)因此在交换成本高昂的场景中比冒泡和普通插入更可控。但它不稳定、不自适应所以通用排序场景中基本不会优先选它。记住选择排序不是用来“快”的而是用来“稳”的。这里的“稳”不是稳定性而是操作数量的可预测性。4. 插入排序扑克牌式局部有序最懂数据的 O(n²)4.1 把新元素插进已经有序的牌堆里插入排序的思路和整理扑克牌完全一样你从左往右看牌手里已经摸到的部分保持有序每次摸到一张新牌就把它往左移动插到正确位置。循环从第二个元素开始因为第一个元素天然构成一个长度为 1 的有序区间。每次把当前元素记为key然后把它和左边已经有序的元素从右往左比较凡是大于key的元素都向右移动一位直到找到key应该插入的位置。def insertion_sort(nums): nums nums[:] n len(nums) for i in range(1, n): key nums[i] j i - 1 while j 0 and nums[j] key: nums[j 1] nums[j] j - 1 nums[j 1] key return nums注意这里用的是“移动”而不是“交换”。如果把key一路交换到前面每交换一次都要做三次赋值用移动加最后落位则每个逆序元素只被赋值一次常数更小。4.2 从“交换”到“移动”插入排序真正的开销插入排序的耗时主要取决于两件事比较次数和元素移动次数。每一次nums[j] key成立意味着左边有一个元素需要往右挪同时也意味着当前这个key和它形成了一个逆序对。如果数组完全升序内层 while 一次都不会进入每个元素只做一次比较总复杂度是O(n)。如果数组完全逆序第i个元素平均要比较并移动约i/2个元素总复杂度回到O(n²)。所以插入排序的开销其实和逆序对数量强相关。数据越有序逆序对越少插入排序就越快。这是它最重要的自适应能力。4.3 为什么“接近有序”是插入排序的高光时刻真实业务里的数据往往不是纯随机数而是带着一定程度的局部有序。比如数据库返回的记录按主键大致有序、日志按时间追加、用户列表按注册时间插入。这类数据里插入排序几乎是最合适的 O(n²) 排序。它和冒泡的区别在于冒泡每轮要从头扫到尾即使已经有序也需要靠“无交换”来提前终止插入排序则天然知道有序区间在哪新元素只需要和邻近元素比较几步就能落位不需要反复扫描整个区间。正因如此很多高级排序算法在执行到小规模子数组时会放弃递归和分治改用插入排序收尾。这不是倒退而是承认一个事实当n很小或者子数组已经接近有序时插入排序的常数开销比归并、快排的递归开销更小。4.4 稳定性与“哨兵”这类小优化插入排序是稳定的。因为内层 while 的条件是nums[j] key相等时不会移动所以相等元素保持原有顺序。这个细节和冒泡一样都是“只在严格大于时交换/移动”带来的稳定性红利。如果还想再抠一点常数可以在数组头部预留一个“哨兵”位置把最小的元素先放到nums[0]这样内层循环就不需要每次判断j 0。但在 Python 这类动态语言里这个优化的收益很容易被其他开销抵消。真要在 C 这类语言里追求极致才值得考虑。5. 三者的正面交锋谁适合小数组、谁适合近似有序、谁适合低交换成本5.1 一张表看懂三种 O(n²) 排序的差异把前面分析过的指标集中到一张表里排序算法最好情况最坏情况比较次数特征交换/移动特征稳定性自适应冒泡排序O(n)O(n²)可提前终止但最坏 n²/2交换次数等于逆序对数稳定带优化时是选择排序O(n²)O(n²)固定 n(n-1)/2最多 n-1 次交换不稳定否插入排序O(n)O(n²)最好 n-1最坏 n²/2移动次数和逆序对相关稳定是这张表里最值得注意的对比是选择排序在“输入越有序”这件事上完全不吃红利冒泡和插入却能吃到。所以在近似有序数据上选择排序反而是三者里表现最差的尽管它交换次数最少。5.2 三种典型场景的选择建议如果你手上是一个长度很小、但近乎有序的数组比如几十个元素且大部分已经排好插入排序是首选。它稳定性好、实现简单、能利用局部有序性。如果你在底层环境里交换数组元素代价极高比如数组元素是很大的结构体而比较 key 很便宜选择排序有独特价值。它的交换次数是可控的不会因为数据乱序而增加。如果你只是教学或演示“相邻交换如何消除逆序对”冒泡排序最直观。但实际工程里同样是稳定且简单的排序插入排序通常比冒泡更值得选。冒泡的主要劣势在于即使数据接近有序它仍然需要一趟一趟地从区间头扫到边界插入排序则总能待在“需要处理的位置”附近。5.3 这三个算法其实是高级排序的种子很多人觉得 O(n²) 排序学完就没用了其实恰好相反。插入排序的“局部有序区间”思想是归并排序合并有序序列、以及某些复杂排序在小规模子问题上“回退”的基础。快速排序的“分区”思想可以看成是在不断选择某个元素作为基准让逆序对按区间快速归位希尔排序也不过是给插入排序加上“大步长预排序”让数据先变得接近有序。所以上篇讲的这三个算法不是孤立的知识点。理解了逆序对、稳定性、自适应再看下篇的希尔、归并、快排时你会更清楚每一个设计决策到底在优化什么。6. 简单排序并不简单三个容易被忽略的工程细节6.1 稳定性会在多字段排序时“二次发挥作用”假设你有一批订单先按客户 ID 排一次再按订单金额排一次。如果第二次排序不稳定那么相同金额的订单之间客户 ID 的顺序可能被打乱。很多业务场景里这就需要把客户 ID 作为第二排序条件传进比较函数sorted(orders, keylambda o: (o.amount, o.customer_id))此时稳定性不再是算法是否“正确”的判据而是一个性能优化如果排序函数支持稳定排序你就不需要把所有字段拼成复合 key也省去了一次额外排序。插入排序和冒泡排序天然稳定选择排序不稳定遇到这种需求时要么换算法要么把全部字段塞进比较函数。6.2 不要用带副作用的比较函数排序算法的正确性极度依赖比较函数的“一致性”。同一个元素和自己比结果必须为相等如果比较函数依赖随机数、全局计数器或可变状态那么排序结果可能完全不可预测甚至导致死循环或越界。这个问题在简单排序里不常见因为教材例子都是数字比较。真实项目里排序对象往往是对象比较函数可能调别人写的方法。当你发现“为什么同样的数组每次排出来不一样”时先别怀疑排序算法检查比较函数是不是有副作用。6.3 小规模数据O(n²) 可能赢过 O(n log n)最后说一个反直觉的点数组只有 20 个或 50 个元素时快速排序、归并排序的递归开销、临时数组分配、函数调用成本可能比插入排序的 n² 次比较还高。这也是为什么很多成熟排序实现会在元素个数小于阈值时切换到插入排序。我自己在实际代码里也反复验证过对几十个几乎有序的元素做插入排序往往比一上来就调用快排模板快得多。不是快排不行而是“大 O”只描述增长趋势不描述常数。排序算法的选择永远要结合数据规模、有序程度、比较成本和交换成本来判断。把这层想明白了你就不会再说“O(n²) 排序一无是处”。它们和 O(n log n) 的算法不是对立关系而是一个连续工具箱里的不同工具。上篇先把这三个基本功打牢下篇聊希尔、归并和快排的时候我们就有共同语言了。