这几年带人入门数据结构问得最多的一类问题就是「八大排序到底该背哪几个」。我的答案一直没变冒泡排序、快速排序、堆排序这三个吃透剩下五个基本能自己推出来。冒泡排序负责给你建立「比较—交换—有序区扩张」的直觉快速排序负责让你理解分治和分区这两个贯穿算法设计的核心套路堆排序负责把你从线性结构拽到树形结构上逼你学会用数组下标模拟完全二叉树。DS 初阶阶段学生最容易犯的错是把三个排序当成三段独立代码背下来考试能默写换一个输入规模就完全不知道谁快谁慢、为什么快为什么慢。这篇内容我打算按「为什么这么设计—代码怎么落到纸上—参数怎么选—哪里会炸」的顺序讲目标读者是刚学完数组和递归、正在啃 DS 初阶排序章节的人也包括工作几年后想把这部分重新梳理一遍的开发者。所有复杂度推导我都会带着你算一遍不丢公式让你自己悟代码用 Python 写因为可读性最好下标逻辑和 C 系语言完全一致你换成 Java 或 C 只是语法差异。文中的实测数据来自我自己那台 8 核 16G 的普通开发机只用来对比量级别拿它当绝对标准。1. 三个排序凭什么值得单独拎出来讲1.1 八大排序的真实分层网上说的「八大排序」一般指冒泡、选择、插入、希尔、归并、快速、堆、计数有的版本把计数换成基数。这八个东西在难度和用途上根本不在一个层面硬把它们并列着背是效率最低的学习方式。我习惯把它们分成三层来看这个分层比单纯的「时间复杂度表」有用得多。第一层是教学型排序冒泡、选择、插入。它们的共同特征是比较次数和交换次数可以直接在纸上画出来适合建立「有序区 / 无序区」这个最基础的概念。第二层是工程型排序快速、归并、堆。这一层的东西真正会出现在标准库和业务代码里特点是都依赖递归或者树形结构都有明显的工程优化空间。第三层是非比较型排序计数、基数、桶排序那一类走的是空间换时间的另一条路和前两层的思维方式完全不同。分层的意义在于你不需要对八个排序投入同等精力。第一层理解思想即可第二层必须能手写并且知道优化点在哪里第三层知道适用条件就够了。而第二层里归并排序因为要额外开数组在内存敏感的场景用得少快速排序和堆排序则是真正被反复用到的两个。1.2 三者的核心指标对照很多人背复杂度表背完就忘原因是没搞清楚每个复杂度是「怎么来的」。我把三者的关键指标列出来后面每个章节我会逐个把推导过程补上你现在先有个整体印象。指标冒泡排序快速排序堆排序平均时间复杂度O(n²)O(n log n)O(n log n)最坏时间复杂度O(n²)O(n²)O(n log n)最好时间复杂度O(n)带提前退出O(n log n)O(n log n)空间复杂度O(1)O(log n) 递归栈O(1)稳定性稳定不稳定不稳定是否原地是是是实际常数因子极大小中等缓存友好度好好差这张表里最值得盯的是两行堆排序的「最坏 O(n log n)」和快速排序的「最坏 O(n²)」。这一对反差是整个排序章节最有意思的地方也是面试里最常被追问的点——既然堆排序最坏情况比快排好为什么工程上还是快排用得更多这个问题我放在第 5 章结合实测数据回答。1.3 学习顺序上的一个建议我的建议是先冒泡、再快排、最后堆排。理由不是难度递增而是思维跳跃的平滑度。冒泡到快排跳的是「从逐个比较到分治」这一步中间还能靠「每次都把最小的冒到前面」和「每次把基准放到正确位置」建立起模糊的对应关系理解成本低。快排到堆排跳的是「从线性扫描到树形结构」这一步跨度大得多你得先在脑子里建立「数组下标即树节点」的映射才能看懂下沉操作在干什么。反过来先学堆排的人八成会卡在建堆那一步然后在「为什么从 n/2-1 开始」这里彻底迷失。这不是智力问题是前置知识没铺好。所以下面我按这个顺序讲。2. 冒泡排序被严重低估的入门样本2.1 从最朴素的版本开始写冒泡排序的思想一句话能说清每一轮把当前无序区里最大的那个元素「冒」到无序区末尾然后无序区缩小一格。写出来是这样的def bubble_sort(a): n len(a) for i in range(n - 1): for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] return a这个版本能跑但有一个很明显的浪费如果某一轮从头到尾一次交换都没发生说明数组已经有序了后面所有的轮次都是白跑。这就是第一个优化点。我在实际教学里会特意让人先用这个朴素版本跑一个「已经排好序的 10000 个元素」的数组看着它磨磨蹭蹭跑满整个循环学生对这个浪费的感受才会具体。内层循环边界n - 1 - i这个写法也值得多说一句。i表示已经冒到末尾的元素个数也就是已经确定位置的数量所以内层只需要处理前面n - i个元素下标上界就是n - 1 - i。很多人手写的时候写成n - 1程序也能出结果但多跑了一部分已经有序的区间白白浪费时间。这种「能跑但不对味」的代码是刷题阶段最容易被忽略的问题。2.2 两个优化点提前退出与有序区边界第一个优化加一个交换标记def bubble_sort_flag(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return a这个改动让最好情况从 O(n²) 变成 O(n)——有序数组只需要扫一遍确认。别小看这一点很多排序算法在「输入已经基本有序」这个场景下表现糟糕而带标记的冒泡是少数能直接吃满这个红利的算法。第二个优化更进一步记录每一轮最后一次交换发生的位置这个位置之后的元素全部已经有序下一轮的内层循环直接以它为边界。def bubble_sort_bound(a): n len(a) end n - 1 while end 0: last 0 for j in range(end): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] last j end last return a这段代码的精妙之处在于last的值本身就是「本轮无序区的右边界」。如果某一轮只有位置 3 发生了交换说明 4 到末尾全都已经有序了下一轮只需要扫到 3。在「前段乱序、后段有序」这种数据分布下这个优化的效果非常明显实测能比朴素版快十倍以上。2.3 复杂度是怎么算出来的冒泡的比较次数推导很直白第一轮比较 n-1 次第二轮 n-2 次一直到 1 次总和是 (n-1) (n-2) ... 1 n(n-1)/2。这是一个关于 n 的二次式所以平均和最坏都是 O(n²)。交换次数在最坏情况完全逆序下等于比较次数也是 n(n-1)/2这也是为什么完全逆序的输入对冒泡来说是最坏情况。空间复杂度是 O(1)因为只用了三个临时变量i、j和交换时的临时空间Python 的元组交换底层也是常数空间。关于稳定性这里有一个细节经常被忽略只有在a[j] a[j1]时才交换写成就会破坏稳定性。原因是相等元素本来不需要动一旦你用相等的那两个就会被互换位置相对顺序被打乱。这个点我在面试里问过不少人能立刻答上来的不到一半。2.4 冒泡真正的价值在哪里说句实话生产代码里没人用冒泡排序。但它的价值不在性能在它是唯一一个能把「比较次数」和「交换次数」同时可视化出来的排序。你在纸上画一遍冒泡的过程能直接看到「每一轮结束时末尾那段一定是有序的」这个不变式invariant。理解了不变式你再看选择排序、插入排序都能一眼说出它们各自维护的不变式是什么。不变式这个思维工具是 DS 初阶里最值钱的东西之一。堆排序里「堆顶是最大值」是不变式快速排序里「基准左边的都不大于它右边的都不小于它」也是不变式。冒泡用最低的成本让你先建立起这个习惯这才是它在教学顺序里排第一的原因。提示如果你的冒泡代码跑出来的结果正确但和别人的交换次数统计不一样先检查内层循环上界是不是n - 1 - i再检查比较用的是还是。这两处是最常见的差异来源。3. 堆排序用数组下标假装一棵树3.1 堆的物理结构和下标映射堆排序的第一步是搞明白一件事堆在物理上就是一个数组树只是我们脑子里的想象。给定一个下标为i的节点它的左孩子下标是2i 1右孩子是2i 2父节点是(i - 1) // 2。这三个公式必须闭着眼睛能写出来因为后面所有的操作都建立在这上面。用一个长度为 8 的数组举例下标 0 到 7下标: 0 1 2 3 4 5 6 7 数组: [9, 7, 8, 3, 6, 5, 2, 1] 树形视角: 9(0) / \ 7(1) 8(2) / \ / \ 3(3) 6(4) 5(5) 2(6) / 1(7)验证一下下标 2 的左孩子是2*21 5值 5右孩子是2*22 6值 2。完全对得上。你可以拿这个数组自己多验证几组直到看到下标就能在脑子里定位到树的哪一层。这套映射成立的前提是完全二叉树——除了最后一层其他层都是满的最后一层的节点从左往右连续排列。正是因为完全二叉树有这个性质才能保证数组中间没有空洞下标映射才不会错位。这也是为什么堆排序的空间复杂度能做到 O(1)换成普通二叉树就得老老实实建节点了。3.2 建堆为什么是 O(n) 而不是 O(n log n)这是堆排序里最反直觉的一个点我见过太多人在这里卡住。先说结论自底向上建堆的总代价是 O(n)。很多人的直觉是「有 n/2 个节点需要下沉每次下沉最多 log n 层所以是 O(n log n)」这个推导错在默认了所有节点都下沉了 log n 层。正确的算法是这样的从最后一个非叶子节点下标n // 2 - 1开始依次往前对每个节点做下沉。堆的叶子节点天然就是合法的堆不需要处理所以只需要处理前面一半。代价怎么算按层来算。高度为 h 的节点叶子算高度 0个数最多是 n / 2^(h1)每个这样的节点下沉的代价是 O(h)。总代价是Σ (h 从 0 到 log n) h * n / 2^(h1) (n/2) * Σ h / 2^h而Σ h / 2^h这个级数h 从 1 到无穷收敛到 2。所以总代价约等于(n/2) * 2 n即 O(n)。换个直观的说法堆里绝大多数节点都在底层而底层节点下沉代价极小0 层或 1 层代价大的节点数量极少高度为 log n 的只有 1 个就是根。这是一种「少数服从多数」的加权平均所以整体是线性的。我当初理解这个推导的方法是画一个节点数和代价的表格把每一层的「节点数 × 下沉层数」乘出来加起来看一眼就明白了。高度 h节点数最多每个下沉代价该层总代价0n/2001n/41n/42n/82n/43n/1633n/16…………log n1log nlog n把最后一列加起来总和小于 n。这就是 O(n) 的全部秘密。3.3 下沉操作的实现细节下沉sift down是堆排序的核心动作把某个节点和它的两个孩子比较如果孩子更大就交换然后继续往下走直到它比两个孩子都大或者到底。写成代码def sift_down(a, start, end): root start while True: child 2 * root 1 if child end: break if child 1 end and a[child 1] a[child]: child 1 if a[root] a[child]: a[root], a[child] a[child], a[root] root child else: break几个细节值得单独拎出来说。第一child end这个判断是退出条件end是当前堆的有效范围右边界堆排序过程中这个边界是不断缩小的。第二child 1 end这个判断是防止右孩子越界同时用a[child1] a[child]选出两个孩子里大的那个——必须选大的选小的会导致父节点比另一个孩子小堆的性质被破坏。第三交换完之后root child把指针挪到孩子位置继续往下这个循环结构比递归更好避免了函数调用开销。我见过一个很典型的错误写法把if a[root] a[child]判断写在 while 的判断条件里然后忘了在else分支 break。结果是死循环因为不满足交换条件时root不变child也不变条件永远成立。这种死循环在小数据量下不容易暴露一上大规模就卡死。3.4 完整的堆排序流程建完大顶堆之后排序的逻辑是把堆顶当前最大值和堆末尾元素交换堆的范围缩小一格然后对新的堆顶做一次下沉恢复堆性质。重复这个过程 n-1 次数组就排好了。def heap_sort(a): n len(a) if n 2: return a # 建堆从最后一个非叶子节点往前逐个下沉 for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n - 1) # 排序每次把堆顶换到末尾堆范围缩小 for end in range(n - 1, 0, -1): a[0], a[end] a[end], a[0] sift_down(a, 0, end - 1) return a跑一遍一个小例子[4, 6, 8, 5, 9]先算n // 2 - 1 1从下标 1 开始。下标 1 的值是 6孩子是下标 3值 5和下标 4值 9大的孩子是 9交换后数组变成[4, 9, 8, 5, 6]6 沉到了底部因为它是叶子了停。接着处理下标 0值 4孩子是下标 1值 9和下标 2值 8大的孩子是 9交换后变成[9, 4, 8, 5, 6]指针挪到下标 1值 4孩子是下标 3值 5和下标 4值 6大的孩子是 6交换后变成[9, 6, 8, 5, 4]。建堆完成堆顶 9 是最大值。排序阶段end 4交换下标 0 和 4变成[4, 6, 8, 5, 9]对[0, 3]范围下沉得到[8, 6, 4, 5, 9]。end 3交换下标 0 和 3变成[5, 6, 4, 8, 9]对[0, 2]下沉得到[6, 5, 4, 8, 9]。end 2交换 0 和 2变成[4, 5, 6, 8, 9]下沉后还是[5, 4, 6, 8, 9]再调整……最终得到[4, 5, 6, 8, 9]。手动推一遍这个过程的价值非常大因为你会在推的过程中发现「每次交换后末尾那段一定是全局最大的有序段」这个不变式这就是堆排序正确性的证明骨架。3.5 堆排序的两个硬伤第一个硬伤是不稳定。交换堆顶和堆末尾这个动作会把末尾元素甩到堆顶跨过了大量元素相等元素的相对顺序很容易被打乱。举个小例子[3a, 3b, 1]建堆后还是[3a, 3b, 1]3a 是堆顶交换堆顶和末尾变成[1, 3b, 3a]两个 3 的相对顺序反了。所以只要你需要稳定性堆排序直接出局。第二个硬伤是缓存不友好。下沉操作访问的下标是跳跃的从i跳到2i1再跳到4i3这种访问模式完全跳出了 CPU 缓存的预取规律。相比之下快速排序和归并排序基本都是顺序访问缓存命中率高得多。这就是为什么理论复杂度一样实际跑起来堆排序往往比快排慢一半以上。我在第 5 章的实测数据里能看到这个差距。注意堆排序虽然是原地排序但它交换的是下标 0 和 end如果你的业务代码在排序后还持有原数组某个位置的引用排序后那个引用指向的内容已经完全变了。这一点在写带索引的排序时特别容易踩坑。4. 快速排序分区才是灵魂4.1 分区的三种写法和边界陷阱快速排序的框架很简单选一个基准把数组分成「不大于基准」和「不小于基准」两段然后递归处理两边。但真正手写的时候九成的人会在分区partition这一步卡住而且卡的方式还挺一致——要么下标越界要么死循环要么分区后基准不在正确位置。先看最经典的单指针挖坑法思路是维护一个「小于区的右边界」i遍历时遇到小于基准的元素就把它挪进小于区def partition_lomuto(a, lo, hi): pivot a[hi] i lo for j in range(lo, hi): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[hi] a[hi], a[i] return i这段代码的好处是返回的下标一定就是基准的最终位置递归时用[lo, p-1]和[p1, hi]就行逻辑清晰。坏处是它在「大量元素等于基准」时会退化——所有等于基准的元素都被归到右边如果数组全是相同的值每次分区只能切掉一个元素递归深度变成 n直接爆栈。第二种是双指针 Hoare 法两个指针从两端往中间走各自找「不该在这边」的元素然后交换def partition_hoare(a, lo, hi): pivot a[lo (hi - lo) // 2] i, j lo, hi while True: while a[i] pivot: i 1 while a[j] pivot: j - 1 if i j: return j a[i], a[j] a[j], a[i] i 1 j - 1Hoare 法的分区更均匀交换次数更少在元素重复度高的情况下表现明显更好。但它有一个大坑返回的j不是基准的最终位置而是左半段的最后一个下标递归时必须写成[lo, j]和[j1, hi]写成[lo, j-1]和[j1, hi]就会漏元素或者无限递归。我第一次写 Hoare 的时候因为这个差一错误调了快一个小时所以这里必须记牢。第三种是三路分区专门对付重复元素多的场景def quick_sort_3way(a, lo, hi): if lo hi: return pivot a[lo (hi - lo) // 2] lt, gt, i lo, hi, lo while i gt: if a[i] pivot: a[lt], a[i] a[i], a[lt] lt 1 i 1 elif a[i] pivot: a[gt], a[i] a[i], a[gt] gt - 1 else: i 1 quick_sort_3way(a, lo, lt - 1) quick_sort_3way(a, gt 1, hi)三路分区把数组分成 pivot、 pivot、 pivot三段中间那段完全有序不用再递归。在处理「只有 0、1、2 三种取值」这类数据时它能一次把等于基准的全部归位效果立竿见影。4.2 基准选择的演进路线基准选得好不好直接决定快排是 O(n log n) 还是 O(n²)。这条演进路线值得完整走一遍因为每一步的动机都很清楚。固定选第一个或最后一个是最朴素的写法代码最简单。它的致命问题是对已经有序的输入完全失效每次分区都只能切掉一个元素递归深度变成 n复杂度退化成 O(n²)。而这个场景在真实业务里并不罕见——比如你从一个已经按时间排好序的表里取数据再做一次按时间排序就正好撞上这个最坏情况。早年有些系统因为这个问题被恶意构造的输入打挂过这属于经典踩坑案例了。随机选基准把最坏情况的概率压到极低随机化之后出现 O(n²) 需要连续多次抽到极端值概率可以忽略。它的代价是每次递归都要调一次随机函数有少量开销而且引入了不确定性调试时两次运行的行为可能不一致。三数取中是我最推荐的默认方案取首、中、尾三个位置的元素把中位数放到基准位置。这一步很便宜三次比较但能有效规避「完全有序」和「完全逆序」这两种最坏输入因为这两种情况下三数取中恰好能选到中间那个值。def median_of_three(a, lo, hi): mid lo (hi - lo) // 2 if a[lo] a[mid]: a[lo], a[mid] a[mid], a[lo] if a[lo] a[hi]: a[lo], a[hi] a[hi], a[lo] if a[mid] a[hi]: a[mid], a[hi] a[hi], a[mid] return mid这段代码跑完之后a[lo] a[mid] a[hi]中位数落到a[mid]。三次比较就完成了非常划算。4.3 小数组切换插入排序的阈值这个优化点很多人知道名字但不知道原因。核心事实是递归的开销在小数组上占比太高。当子数组长度小于 16 左右时快速排序的递归调用、分区开销加起来已经超过了它相比插入排序省下的比较次数。插入排序虽然复杂度是 O(n²)但在 n 很小时常数因子极小实际更快。阈值取多少这个没有绝对答案不同语言、不同硬件的最佳值不一样。C 系语言的主流标准库一般取 16 左右Java 的Arrays.sort对小数组也是走插入排序。我在 Python 环境下实测过 8、16、24、32 几档16 附近是最优区再往上增加收益就很小了。你如果自己实现先用 16然后拿自己业务里的数据规模测一下别完全照抄。THRESHOLD 16 def insertion_sort_range(a, lo, hi): for i in range(lo 1, hi 1): cur a[i] j i - 1 while j lo and a[j] cur: a[j 1] a[j] j - 1 a[j 1] cur def quick_sort_hybrid(a, lo, hi): if hi - lo 1 THRESHOLD: insertion_sort_range(a, lo, hi) return p partition_hoare(a, lo, hi) quick_sort_hybrid(a, lo, p) quick_sort_hybrid(a, p 1, hi)注意insertion_sort_range里的条件a[j] cur用严格大于才能保证插入排序是稳定的。虽然快排整体不稳定但小段内部保持稳定有时候对下游有好处能省一点麻烦就省一点。4.4 递归深度和栈溢出快速排序的空间复杂度 O(log n) 指的是递归栈的深度。平均情况下是 log n 层但如果碰到最坏情况每次分区极不均匀深度会接近 n。Python 默认递归深度限制是 1000也就是说数组长度超过 1000 且有退化倾向时就可能抛RecursionError。解决办法有三个按推荐程度排序第一递归较短的半边循环处理较长的半边尾递归优化。这样递归深度最多是 log n永远不会爆栈def quick_sort_tail(a, lo, hi): while lo hi: if hi - lo 1 THRESHOLD: insertion_sort_range(a, lo, hi) return p partition_hoare(a, lo, hi) if p - lo hi - p: quick_sort_tail(a, lo, p) lo p 1 else: quick_sort_tail(a, p 1, hi) hi p第二显式维护一个栈把递归改成迭代。代码会长一点但彻底不受递归深度限制我在处理超大规模数据时更偏好这个写法。第三兜底策略记录递归深度超过2 * log2(n)就切换到堆排序。这是 introsort 的思路也是 C 标准库std::sort的做法。它同时拿到了快排的平均性能和堆排的最坏保证是工程上最稳的方案。提示如果你在 Python 里调sys.setrecursionlimit来绕过这个问题我只能说治标不治本。递归深度上万的时候即使不抛异常也有可能把解释器栈撑爆导致进程直接崩掉连异常都抓不到。5. 三种排序放在一起跑差别到底有多大5.1 测试环境和数据构造光看复杂度表没有体感我把自己跑的几组数据贴出来。环境是一台 8 核 16G 的普通开发机Python 3.10测的是纯 Python 实现所以绝对值比 C 系慢很多你看横向比例就行别揪着秒数。测试数据分四种这四种基本覆盖了真实场景随机无序random.shuffle打乱最常规的情况。完全有序list(range(n))用来测提前退化和三数取中的效果。完全逆序list(range(n, 0, -1))冒泡的最坏情况。大量重复从 0 到 9 随机取值用来打三路快排和 Hoare 的对比。测试前有个必须做的动作每种情况跑三次取中位数而且要确认排序结果是正确的跟sorted()的结果比对。我第一次测的时候忘了校验结果发现某个版本的分区写错了虽然跑得快但结果是残的白测一轮。5.2 实测数据n 10000 的耗时单位秒场景朴素冒泡优化冒泡堆排序快排三数取中插入三路快排随机无序7.427.380.0610.0280.031完全有序5.100.00090.0520.0180.026完全逆序7.857.700.0570.0190.027大量重复6.936.900.0590.0410.017n 100000 的耗时单位秒朴素冒泡在这个量级下要跑十几分钟直接标注不测场景优化冒泡堆排序快排三数取中插入三路快排随机无序约 7400.820.350.39完全有序0.0080.700.220.31完全逆序约 7800.790.230.32大量重复约 7000.800.550.21n 1000000能跑的就剩堆排和快排了场景堆排序快排三数取中插入三路快排随机无序10.84.65.0完全有序9.63.14.2完全逆序10.13.24.3大量重复10.57.42.85.3 数据里能读出什么第一堆排序的数据几乎不随输入分布变化始终在 10 秒出头。这就是「最坏 O(n log n)」的实际表现它对你的输入长什么样完全不关心。这种可预测性在某些场景下比绝对速度更有价值比如你需要给一个实时系统估算上界的时候。第二快排在所有常规场景下都比堆排快一倍以上差距来自两部分一是堆排的缓存不友好二是快排的分区是顺序扫的预取效率高。这个差距大到什么程度大到「快排最坏 O(n²)」这个理论缺陷在实际工程里根本不算事——因为你只要加上三数取中再稍微注意一下递归深度退化到 O(n²) 的概率低到你一辈子碰不上。第三三路快排在重复元素多的场景下碾压其他两个百万级数据只用了 2.8 秒而普通快排要 7.4 秒。差距太明显了。所以如果你的业务数据有明显的重复度比如订单状态、用户等级这种枚举值当排序键直接上三路快排别犹豫。第四优化冒泡在完全有序的输入上快得离谱0.0009 秒比堆排和快排都快。这个数据经常被拿来当反面教材说「冒泡并不是一无是处」。我的看法是这个优势成立的前提是你确定输入基本有序而且只做一次排序。一旦输入分布不确定这个优势立刻变成劣势。5.4 选型建议需要稳定性这三个都不行去用归并或者sorted()。数据量大、分布随机快速排序三数取中 小数组切插入 尾递归。数据重复度高三路快排。需要严格的时间上界堆排序或者 introsort 混合方案。数据几乎有序优化冒泡带边界记录或者直接插入排序。数据量小于 20别想了插入排序最快。6. 常见问题与排查实录6.1 结果「看起来对」但少元素或多元素这是分区写错最典型的症状。表现是排序后的数组长度和原数组一样但内容对不上或者部分元素重复、部分元素消失。根因几乎都是分区的两个区间没能覆盖整个[lo, hi]中间漏掉了一段。排查方法很简单在分区函数里加一行打印把lo、hi、分区点、分区后的数组全打出来人工核对两个区间是否严丝合缝。更省事的办法是写一个校验函数def check_partition(a, lo, hi, p): pivot a[p] assert all(a[i] pivot for i in range(lo, p)), 左段有大于基准的 assert all(a[i] pivot for i in range(p 1, hi 1)), 右段有小于基准的对着小数组长度 5 到 8跑几百组随机数据如果全部通过分区的边界大概率没问题。别一上来就拿长度 10000 的数组测出了错你根本定位不到哪一步走的。6.2 快排跑得莫名其妙慢如果快排在随机数据上表现正常但在某类特定数据上慢了十几倍先怀疑两件事基准选择策略和重复元素。判断方法很直接——加一行计数记录最大递归深度。如果最大深度接近 n基本就锁定是基准退化如果深度正常但交换次数暴涨那就是重复元素导致的。还有一个隐蔽原因你测的数据本身就是有序的。我踩过一次从数据库里读出来的数据默认按主键排好序了我以为拿到的是随机的结果测试结果怎么调都不对。后来发现是数据源的问题白折腾两小时。所以测之前一定先打乱或者校验一下数据的分布。6.3 堆排序建堆没生效症状是排序结果大体有序但局部乱或者末尾几个元素位置不对。先检查建堆的循环是不是range(n // 2 - 1, -1, -1)——注意是-1结尾很多人写成range(n // 2 - 1, 0, -1)漏掉了下标 0 那个根节点。根节点不处理最大元素就不在堆顶整个排序的根基就错了。第二个检查点是sift_down的end参数。建堆阶段传的是n - 1排序阶段每次传的是end - 1。这两个值搞混了会有两个后果要么下沉越界访问要么下沉范围大了把已经排好的元素又搅乱了。6.4 常见问题速查表症状最可能的原因快速验证递归深度异常大基准选到了极值三数取中没生效打印最大递归深度看是否接近 n数组越界分区指针没加边界检查用长度 2 和 3 的数组测无限循环分区时相等元素既不移也不换检查循环里的i 1分支排序结果少了元素两个递归区间没覆盖全校验[lo, p]和[p1, hi]的并集堆排结果末尾错乱建堆起点写成n // 2或漏了根打印建堆后的数组确认a[0]是最大值冒泡优化后结果错边界变量end更新时机不对用只有前 3 个元素乱序的数组测大数据下进程崩溃递归栈溢出换成尾递归或显式栈版本6.5 几条踩出来的经验最后分享几个我自己踩出来的点都属于文档上不会写、但实际会恶心你半天的类型。第一交换条件用严格大小比较。不管是冒泡的、插入的、还是堆下沉里的只要涉及「相等时不动」的语义就必须是严格比较。一旦写成稳定性直接没了而且很多时候结果还是对的你根本发现不了直到某天业务方告诉你「同样的订单两次排序出来的顺序不一样」。第二写排序一定先测小数组全排列。长度 4 或 5 的数组全排列也就几十上百种情况跑一遍全过基本可以确认逻辑正确。这比拿大数组瞎试效率高得多也是我现在的标准动作。第三复杂度表只能做初筛不能做决策。堆排和快排理论复杂度一样实测差一倍多三路快排的理论复杂度和普通快排一样在重复数据上快 2.6 倍。真正选算法的时候拿你的真实数据跑一遍比背十张复杂度表都有用。第四别在生产代码里手写这些排序。标准库的排序实现是几十年工程优化的结果混合了多种策略和边界处理你手写的版本几乎不可能超过它。手写排序的价值在于理解思想、应对笔试面试、以及在极特殊场景下做定制比如按对象某个字段排序且要保持稳定性这时候你用sorted(key...)就够了也不用自己写。 
长河君 · 2026/10/27 2:33:19 · 阅读 1.2k 八大排序入门：吃透冒泡、快速与堆排序的复杂度与工程选型
这几年带人入门数据结构问得最多的一类问题就是「八大排序到底该背哪几个」。我的答案一直没变冒泡排序、快速排序、堆排序这三个吃透剩下五个基本能自己推出来。冒泡排序负责给你建立「比较—交换—有序区扩张」的直觉快速排序负责让你理解分治和分区这两个贯穿算法设计的核心套路堆排序负责把你从线性结构拽到树形结构上逼你学会用数组下标模拟完全二叉树。DS 初阶阶段学生最容易犯的错是把三个排序当成三段独立代码背下来考试能默写换一个输入规模就完全不知道谁快谁慢、为什么快为什么慢。这篇内容我打算按「为什么这么设计—代码怎么落到纸上—参数怎么选—哪里会炸」的顺序讲目标读者是刚学完数组和递归、正在啃 DS 初阶排序章节的人也包括工作几年后想把这部分重新梳理一遍的开发者。所有复杂度推导我都会带着你算一遍不丢公式让你自己悟代码用 Python 写因为可读性最好下标逻辑和 C 系语言完全一致你换成 Java 或 C 只是语法差异。文中的实测数据来自我自己那台 8 核 16G 的普通开发机只用来对比量级别拿它当绝对标准。1. 三个排序凭什么值得单独拎出来讲1.1 八大排序的真实分层网上说的「八大排序」一般指冒泡、选择、插入、希尔、归并、快速、堆、计数有的版本把计数换成基数。这八个东西在难度和用途上根本不在一个层面硬把它们并列着背是效率最低的学习方式。我习惯把它们分成三层来看这个分层比单纯的「时间复杂度表」有用得多。第一层是教学型排序冒泡、选择、插入。它们的共同特征是比较次数和交换次数可以直接在纸上画出来适合建立「有序区 / 无序区」这个最基础的概念。第二层是工程型排序快速、归并、堆。这一层的东西真正会出现在标准库和业务代码里特点是都依赖递归或者树形结构都有明显的工程优化空间。第三层是非比较型排序计数、基数、桶排序那一类走的是空间换时间的另一条路和前两层的思维方式完全不同。分层的意义在于你不需要对八个排序投入同等精力。第一层理解思想即可第二层必须能手写并且知道优化点在哪里第三层知道适用条件就够了。而第二层里归并排序因为要额外开数组在内存敏感的场景用得少快速排序和堆排序则是真正被反复用到的两个。1.2 三者的核心指标对照很多人背复杂度表背完就忘原因是没搞清楚每个复杂度是「怎么来的」。我把三者的关键指标列出来后面每个章节我会逐个把推导过程补上你现在先有个整体印象。指标冒泡排序快速排序堆排序平均时间复杂度O(n²)O(n log n)O(n log n)最坏时间复杂度O(n²)O(n²)O(n log n)最好时间复杂度O(n)带提前退出O(n log n)O(n log n)空间复杂度O(1)O(log n) 递归栈O(1)稳定性稳定不稳定不稳定是否原地是是是实际常数因子极大小中等缓存友好度好好差这张表里最值得盯的是两行堆排序的「最坏 O(n log n)」和快速排序的「最坏 O(n²)」。这一对反差是整个排序章节最有意思的地方也是面试里最常被追问的点——既然堆排序最坏情况比快排好为什么工程上还是快排用得更多这个问题我放在第 5 章结合实测数据回答。1.3 学习顺序上的一个建议我的建议是先冒泡、再快排、最后堆排。理由不是难度递增而是思维跳跃的平滑度。冒泡到快排跳的是「从逐个比较到分治」这一步中间还能靠「每次都把最小的冒到前面」和「每次把基准放到正确位置」建立起模糊的对应关系理解成本低。快排到堆排跳的是「从线性扫描到树形结构」这一步跨度大得多你得先在脑子里建立「数组下标即树节点」的映射才能看懂下沉操作在干什么。反过来先学堆排的人八成会卡在建堆那一步然后在「为什么从 n/2-1 开始」这里彻底迷失。这不是智力问题是前置知识没铺好。所以下面我按这个顺序讲。2. 冒泡排序被严重低估的入门样本2.1 从最朴素的版本开始写冒泡排序的思想一句话能说清每一轮把当前无序区里最大的那个元素「冒」到无序区末尾然后无序区缩小一格。写出来是这样的def bubble_sort(a): n len(a) for i in range(n - 1): for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] return a这个版本能跑但有一个很明显的浪费如果某一轮从头到尾一次交换都没发生说明数组已经有序了后面所有的轮次都是白跑。这就是第一个优化点。我在实际教学里会特意让人先用这个朴素版本跑一个「已经排好序的 10000 个元素」的数组看着它磨磨蹭蹭跑满整个循环学生对这个浪费的感受才会具体。内层循环边界n - 1 - i这个写法也值得多说一句。i表示已经冒到末尾的元素个数也就是已经确定位置的数量所以内层只需要处理前面n - i个元素下标上界就是n - 1 - i。很多人手写的时候写成n - 1程序也能出结果但多跑了一部分已经有序的区间白白浪费时间。这种「能跑但不对味」的代码是刷题阶段最容易被忽略的问题。2.2 两个优化点提前退出与有序区边界第一个优化加一个交换标记def bubble_sort_flag(a): n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return a这个改动让最好情况从 O(n²) 变成 O(n)——有序数组只需要扫一遍确认。别小看这一点很多排序算法在「输入已经基本有序」这个场景下表现糟糕而带标记的冒泡是少数能直接吃满这个红利的算法。第二个优化更进一步记录每一轮最后一次交换发生的位置这个位置之后的元素全部已经有序下一轮的内层循环直接以它为边界。def bubble_sort_bound(a): n len(a) end n - 1 while end 0: last 0 for j in range(end): if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] last j end last return a这段代码的精妙之处在于last的值本身就是「本轮无序区的右边界」。如果某一轮只有位置 3 发生了交换说明 4 到末尾全都已经有序了下一轮只需要扫到 3。在「前段乱序、后段有序」这种数据分布下这个优化的效果非常明显实测能比朴素版快十倍以上。2.3 复杂度是怎么算出来的冒泡的比较次数推导很直白第一轮比较 n-1 次第二轮 n-2 次一直到 1 次总和是 (n-1) (n-2) ... 1 n(n-1)/2。这是一个关于 n 的二次式所以平均和最坏都是 O(n²)。交换次数在最坏情况完全逆序下等于比较次数也是 n(n-1)/2这也是为什么完全逆序的输入对冒泡来说是最坏情况。空间复杂度是 O(1)因为只用了三个临时变量i、j和交换时的临时空间Python 的元组交换底层也是常数空间。关于稳定性这里有一个细节经常被忽略只有在a[j] a[j1]时才交换写成就会破坏稳定性。原因是相等元素本来不需要动一旦你用相等的那两个就会被互换位置相对顺序被打乱。这个点我在面试里问过不少人能立刻答上来的不到一半。2.4 冒泡真正的价值在哪里说句实话生产代码里没人用冒泡排序。但它的价值不在性能在它是唯一一个能把「比较次数」和「交换次数」同时可视化出来的排序。你在纸上画一遍冒泡的过程能直接看到「每一轮结束时末尾那段一定是有序的」这个不变式invariant。理解了不变式你再看选择排序、插入排序都能一眼说出它们各自维护的不变式是什么。不变式这个思维工具是 DS 初阶里最值钱的东西之一。堆排序里「堆顶是最大值」是不变式快速排序里「基准左边的都不大于它右边的都不小于它」也是不变式。冒泡用最低的成本让你先建立起这个习惯这才是它在教学顺序里排第一的原因。提示如果你的冒泡代码跑出来的结果正确但和别人的交换次数统计不一样先检查内层循环上界是不是n - 1 - i再检查比较用的是还是。这两处是最常见的差异来源。3. 堆排序用数组下标假装一棵树3.1 堆的物理结构和下标映射堆排序的第一步是搞明白一件事堆在物理上就是一个数组树只是我们脑子里的想象。给定一个下标为i的节点它的左孩子下标是2i 1右孩子是2i 2父节点是(i - 1) // 2。这三个公式必须闭着眼睛能写出来因为后面所有的操作都建立在这上面。用一个长度为 8 的数组举例下标 0 到 7下标: 0 1 2 3 4 5 6 7 数组: [9, 7, 8, 3, 6, 5, 2, 1] 树形视角: 9(0) / \ 7(1) 8(2) / \ / \ 3(3) 6(4) 5(5) 2(6) / 1(7)验证一下下标 2 的左孩子是2*21 5值 5右孩子是2*22 6值 2。完全对得上。你可以拿这个数组自己多验证几组直到看到下标就能在脑子里定位到树的哪一层。这套映射成立的前提是完全二叉树——除了最后一层其他层都是满的最后一层的节点从左往右连续排列。正是因为完全二叉树有这个性质才能保证数组中间没有空洞下标映射才不会错位。这也是为什么堆排序的空间复杂度能做到 O(1)换成普通二叉树就得老老实实建节点了。3.2 建堆为什么是 O(n) 而不是 O(n log n)这是堆排序里最反直觉的一个点我见过太多人在这里卡住。先说结论自底向上建堆的总代价是 O(n)。很多人的直觉是「有 n/2 个节点需要下沉每次下沉最多 log n 层所以是 O(n log n)」这个推导错在默认了所有节点都下沉了 log n 层。正确的算法是这样的从最后一个非叶子节点下标n // 2 - 1开始依次往前对每个节点做下沉。堆的叶子节点天然就是合法的堆不需要处理所以只需要处理前面一半。代价怎么算按层来算。高度为 h 的节点叶子算高度 0个数最多是 n / 2^(h1)每个这样的节点下沉的代价是 O(h)。总代价是Σ (h 从 0 到 log n) h * n / 2^(h1) (n/2) * Σ h / 2^h而Σ h / 2^h这个级数h 从 1 到无穷收敛到 2。所以总代价约等于(n/2) * 2 n即 O(n)。换个直观的说法堆里绝大多数节点都在底层而底层节点下沉代价极小0 层或 1 层代价大的节点数量极少高度为 log n 的只有 1 个就是根。这是一种「少数服从多数」的加权平均所以整体是线性的。我当初理解这个推导的方法是画一个节点数和代价的表格把每一层的「节点数 × 下沉层数」乘出来加起来看一眼就明白了。高度 h节点数最多每个下沉代价该层总代价0n/2001n/41n/42n/82n/43n/1633n/16…………log n1log nlog n把最后一列加起来总和小于 n。这就是 O(n) 的全部秘密。3.3 下沉操作的实现细节下沉sift down是堆排序的核心动作把某个节点和它的两个孩子比较如果孩子更大就交换然后继续往下走直到它比两个孩子都大或者到底。写成代码def sift_down(a, start, end): root start while True: child 2 * root 1 if child end: break if child 1 end and a[child 1] a[child]: child 1 if a[root] a[child]: a[root], a[child] a[child], a[root] root child else: break几个细节值得单独拎出来说。第一child end这个判断是退出条件end是当前堆的有效范围右边界堆排序过程中这个边界是不断缩小的。第二child 1 end这个判断是防止右孩子越界同时用a[child1] a[child]选出两个孩子里大的那个——必须选大的选小的会导致父节点比另一个孩子小堆的性质被破坏。第三交换完之后root child把指针挪到孩子位置继续往下这个循环结构比递归更好避免了函数调用开销。我见过一个很典型的错误写法把if a[root] a[child]判断写在 while 的判断条件里然后忘了在else分支 break。结果是死循环因为不满足交换条件时root不变child也不变条件永远成立。这种死循环在小数据量下不容易暴露一上大规模就卡死。3.4 完整的堆排序流程建完大顶堆之后排序的逻辑是把堆顶当前最大值和堆末尾元素交换堆的范围缩小一格然后对新的堆顶做一次下沉恢复堆性质。重复这个过程 n-1 次数组就排好了。def heap_sort(a): n len(a) if n 2: return a # 建堆从最后一个非叶子节点往前逐个下沉 for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n - 1) # 排序每次把堆顶换到末尾堆范围缩小 for end in range(n - 1, 0, -1): a[0], a[end] a[end], a[0] sift_down(a, 0, end - 1) return a跑一遍一个小例子[4, 6, 8, 5, 9]先算n // 2 - 1 1从下标 1 开始。下标 1 的值是 6孩子是下标 3值 5和下标 4值 9大的孩子是 9交换后数组变成[4, 9, 8, 5, 6]6 沉到了底部因为它是叶子了停。接着处理下标 0值 4孩子是下标 1值 9和下标 2值 8大的孩子是 9交换后变成[9, 4, 8, 5, 6]指针挪到下标 1值 4孩子是下标 3值 5和下标 4值 6大的孩子是 6交换后变成[9, 6, 8, 5, 4]。建堆完成堆顶 9 是最大值。排序阶段end 4交换下标 0 和 4变成[4, 6, 8, 5, 9]对[0, 3]范围下沉得到[8, 6, 4, 5, 9]。end 3交换下标 0 和 3变成[5, 6, 4, 8, 9]对[0, 2]下沉得到[6, 5, 4, 8, 9]。end 2交换 0 和 2变成[4, 5, 6, 8, 9]下沉后还是[5, 4, 6, 8, 9]再调整……最终得到[4, 5, 6, 8, 9]。手动推一遍这个过程的价值非常大因为你会在推的过程中发现「每次交换后末尾那段一定是全局最大的有序段」这个不变式这就是堆排序正确性的证明骨架。3.5 堆排序的两个硬伤第一个硬伤是不稳定。交换堆顶和堆末尾这个动作会把末尾元素甩到堆顶跨过了大量元素相等元素的相对顺序很容易被打乱。举个小例子[3a, 3b, 1]建堆后还是[3a, 3b, 1]3a 是堆顶交换堆顶和末尾变成[1, 3b, 3a]两个 3 的相对顺序反了。所以只要你需要稳定性堆排序直接出局。第二个硬伤是缓存不友好。下沉操作访问的下标是跳跃的从i跳到2i1再跳到4i3这种访问模式完全跳出了 CPU 缓存的预取规律。相比之下快速排序和归并排序基本都是顺序访问缓存命中率高得多。这就是为什么理论复杂度一样实际跑起来堆排序往往比快排慢一半以上。我在第 5 章的实测数据里能看到这个差距。注意堆排序虽然是原地排序但它交换的是下标 0 和 end如果你的业务代码在排序后还持有原数组某个位置的引用排序后那个引用指向的内容已经完全变了。这一点在写带索引的排序时特别容易踩坑。4. 快速排序分区才是灵魂4.1 分区的三种写法和边界陷阱快速排序的框架很简单选一个基准把数组分成「不大于基准」和「不小于基准」两段然后递归处理两边。但真正手写的时候九成的人会在分区partition这一步卡住而且卡的方式还挺一致——要么下标越界要么死循环要么分区后基准不在正确位置。先看最经典的单指针挖坑法思路是维护一个「小于区的右边界」i遍历时遇到小于基准的元素就把它挪进小于区def partition_lomuto(a, lo, hi): pivot a[hi] i lo for j in range(lo, hi): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[hi] a[hi], a[i] return i这段代码的好处是返回的下标一定就是基准的最终位置递归时用[lo, p-1]和[p1, hi]就行逻辑清晰。坏处是它在「大量元素等于基准」时会退化——所有等于基准的元素都被归到右边如果数组全是相同的值每次分区只能切掉一个元素递归深度变成 n直接爆栈。第二种是双指针 Hoare 法两个指针从两端往中间走各自找「不该在这边」的元素然后交换def partition_hoare(a, lo, hi): pivot a[lo (hi - lo) // 2] i, j lo, hi while True: while a[i] pivot: i 1 while a[j] pivot: j - 1 if i j: return j a[i], a[j] a[j], a[i] i 1 j - 1Hoare 法的分区更均匀交换次数更少在元素重复度高的情况下表现明显更好。但它有一个大坑返回的j不是基准的最终位置而是左半段的最后一个下标递归时必须写成[lo, j]和[j1, hi]写成[lo, j-1]和[j1, hi]就会漏元素或者无限递归。我第一次写 Hoare 的时候因为这个差一错误调了快一个小时所以这里必须记牢。第三种是三路分区专门对付重复元素多的场景def quick_sort_3way(a, lo, hi): if lo hi: return pivot a[lo (hi - lo) // 2] lt, gt, i lo, hi, lo while i gt: if a[i] pivot: a[lt], a[i] a[i], a[lt] lt 1 i 1 elif a[i] pivot: a[gt], a[i] a[i], a[gt] gt - 1 else: i 1 quick_sort_3way(a, lo, lt - 1) quick_sort_3way(a, gt 1, hi)三路分区把数组分成 pivot、 pivot、 pivot三段中间那段完全有序不用再递归。在处理「只有 0、1、2 三种取值」这类数据时它能一次把等于基准的全部归位效果立竿见影。4.2 基准选择的演进路线基准选得好不好直接决定快排是 O(n log n) 还是 O(n²)。这条演进路线值得完整走一遍因为每一步的动机都很清楚。固定选第一个或最后一个是最朴素的写法代码最简单。它的致命问题是对已经有序的输入完全失效每次分区都只能切掉一个元素递归深度变成 n复杂度退化成 O(n²)。而这个场景在真实业务里并不罕见——比如你从一个已经按时间排好序的表里取数据再做一次按时间排序就正好撞上这个最坏情况。早年有些系统因为这个问题被恶意构造的输入打挂过这属于经典踩坑案例了。随机选基准把最坏情况的概率压到极低随机化之后出现 O(n²) 需要连续多次抽到极端值概率可以忽略。它的代价是每次递归都要调一次随机函数有少量开销而且引入了不确定性调试时两次运行的行为可能不一致。三数取中是我最推荐的默认方案取首、中、尾三个位置的元素把中位数放到基准位置。这一步很便宜三次比较但能有效规避「完全有序」和「完全逆序」这两种最坏输入因为这两种情况下三数取中恰好能选到中间那个值。def median_of_three(a, lo, hi): mid lo (hi - lo) // 2 if a[lo] a[mid]: a[lo], a[mid] a[mid], a[lo] if a[lo] a[hi]: a[lo], a[hi] a[hi], a[lo] if a[mid] a[hi]: a[mid], a[hi] a[hi], a[mid] return mid这段代码跑完之后a[lo] a[mid] a[hi]中位数落到a[mid]。三次比较就完成了非常划算。4.3 小数组切换插入排序的阈值这个优化点很多人知道名字但不知道原因。核心事实是递归的开销在小数组上占比太高。当子数组长度小于 16 左右时快速排序的递归调用、分区开销加起来已经超过了它相比插入排序省下的比较次数。插入排序虽然复杂度是 O(n²)但在 n 很小时常数因子极小实际更快。阈值取多少这个没有绝对答案不同语言、不同硬件的最佳值不一样。C 系语言的主流标准库一般取 16 左右Java 的Arrays.sort对小数组也是走插入排序。我在 Python 环境下实测过 8、16、24、32 几档16 附近是最优区再往上增加收益就很小了。你如果自己实现先用 16然后拿自己业务里的数据规模测一下别完全照抄。THRESHOLD 16 def insertion_sort_range(a, lo, hi): for i in range(lo 1, hi 1): cur a[i] j i - 1 while j lo and a[j] cur: a[j 1] a[j] j - 1 a[j 1] cur def quick_sort_hybrid(a, lo, hi): if hi - lo 1 THRESHOLD: insertion_sort_range(a, lo, hi) return p partition_hoare(a, lo, hi) quick_sort_hybrid(a, lo, p) quick_sort_hybrid(a, p 1, hi)注意insertion_sort_range里的条件a[j] cur用严格大于才能保证插入排序是稳定的。虽然快排整体不稳定但小段内部保持稳定有时候对下游有好处能省一点麻烦就省一点。4.4 递归深度和栈溢出快速排序的空间复杂度 O(log n) 指的是递归栈的深度。平均情况下是 log n 层但如果碰到最坏情况每次分区极不均匀深度会接近 n。Python 默认递归深度限制是 1000也就是说数组长度超过 1000 且有退化倾向时就可能抛RecursionError。解决办法有三个按推荐程度排序第一递归较短的半边循环处理较长的半边尾递归优化。这样递归深度最多是 log n永远不会爆栈def quick_sort_tail(a, lo, hi): while lo hi: if hi - lo 1 THRESHOLD: insertion_sort_range(a, lo, hi) return p partition_hoare(a, lo, hi) if p - lo hi - p: quick_sort_tail(a, lo, p) lo p 1 else: quick_sort_tail(a, p 1, hi) hi p第二显式维护一个栈把递归改成迭代。代码会长一点但彻底不受递归深度限制我在处理超大规模数据时更偏好这个写法。第三兜底策略记录递归深度超过2 * log2(n)就切换到堆排序。这是 introsort 的思路也是 C 标准库std::sort的做法。它同时拿到了快排的平均性能和堆排的最坏保证是工程上最稳的方案。提示如果你在 Python 里调sys.setrecursionlimit来绕过这个问题我只能说治标不治本。递归深度上万的时候即使不抛异常也有可能把解释器栈撑爆导致进程直接崩掉连异常都抓不到。5. 三种排序放在一起跑差别到底有多大5.1 测试环境和数据构造光看复杂度表没有体感我把自己跑的几组数据贴出来。环境是一台 8 核 16G 的普通开发机Python 3.10测的是纯 Python 实现所以绝对值比 C 系慢很多你看横向比例就行别揪着秒数。测试数据分四种这四种基本覆盖了真实场景随机无序random.shuffle打乱最常规的情况。完全有序list(range(n))用来测提前退化和三数取中的效果。完全逆序list(range(n, 0, -1))冒泡的最坏情况。大量重复从 0 到 9 随机取值用来打三路快排和 Hoare 的对比。测试前有个必须做的动作每种情况跑三次取中位数而且要确认排序结果是正确的跟sorted()的结果比对。我第一次测的时候忘了校验结果发现某个版本的分区写错了虽然跑得快但结果是残的白测一轮。5.2 实测数据n 10000 的耗时单位秒场景朴素冒泡优化冒泡堆排序快排三数取中插入三路快排随机无序7.427.380.0610.0280.031完全有序5.100.00090.0520.0180.026完全逆序7.857.700.0570.0190.027大量重复6.936.900.0590.0410.017n 100000 的耗时单位秒朴素冒泡在这个量级下要跑十几分钟直接标注不测场景优化冒泡堆排序快排三数取中插入三路快排随机无序约 7400.820.350.39完全有序0.0080.700.220.31完全逆序约 7800.790.230.32大量重复约 7000.800.550.21n 1000000能跑的就剩堆排和快排了场景堆排序快排三数取中插入三路快排随机无序10.84.65.0完全有序9.63.14.2完全逆序10.13.24.3大量重复10.57.42.85.3 数据里能读出什么第一堆排序的数据几乎不随输入分布变化始终在 10 秒出头。这就是「最坏 O(n log n)」的实际表现它对你的输入长什么样完全不关心。这种可预测性在某些场景下比绝对速度更有价值比如你需要给一个实时系统估算上界的时候。第二快排在所有常规场景下都比堆排快一倍以上差距来自两部分一是堆排的缓存不友好二是快排的分区是顺序扫的预取效率高。这个差距大到什么程度大到「快排最坏 O(n²)」这个理论缺陷在实际工程里根本不算事——因为你只要加上三数取中再稍微注意一下递归深度退化到 O(n²) 的概率低到你一辈子碰不上。第三三路快排在重复元素多的场景下碾压其他两个百万级数据只用了 2.8 秒而普通快排要 7.4 秒。差距太明显了。所以如果你的业务数据有明显的重复度比如订单状态、用户等级这种枚举值当排序键直接上三路快排别犹豫。第四优化冒泡在完全有序的输入上快得离谱0.0009 秒比堆排和快排都快。这个数据经常被拿来当反面教材说「冒泡并不是一无是处」。我的看法是这个优势成立的前提是你确定输入基本有序而且只做一次排序。一旦输入分布不确定这个优势立刻变成劣势。5.4 选型建议需要稳定性这三个都不行去用归并或者sorted()。数据量大、分布随机快速排序三数取中 小数组切插入 尾递归。数据重复度高三路快排。需要严格的时间上界堆排序或者 introsort 混合方案。数据几乎有序优化冒泡带边界记录或者直接插入排序。数据量小于 20别想了插入排序最快。6. 常见问题与排查实录6.1 结果「看起来对」但少元素或多元素这是分区写错最典型的症状。表现是排序后的数组长度和原数组一样但内容对不上或者部分元素重复、部分元素消失。根因几乎都是分区的两个区间没能覆盖整个[lo, hi]中间漏掉了一段。排查方法很简单在分区函数里加一行打印把lo、hi、分区点、分区后的数组全打出来人工核对两个区间是否严丝合缝。更省事的办法是写一个校验函数def check_partition(a, lo, hi, p): pivot a[p] assert all(a[i] pivot for i in range(lo, p)), 左段有大于基准的 assert all(a[i] pivot for i in range(p 1, hi 1)), 右段有小于基准的对着小数组长度 5 到 8跑几百组随机数据如果全部通过分区的边界大概率没问题。别一上来就拿长度 10000 的数组测出了错你根本定位不到哪一步走的。6.2 快排跑得莫名其妙慢如果快排在随机数据上表现正常但在某类特定数据上慢了十几倍先怀疑两件事基准选择策略和重复元素。判断方法很直接——加一行计数记录最大递归深度。如果最大深度接近 n基本就锁定是基准退化如果深度正常但交换次数暴涨那就是重复元素导致的。还有一个隐蔽原因你测的数据本身就是有序的。我踩过一次从数据库里读出来的数据默认按主键排好序了我以为拿到的是随机的结果测试结果怎么调都不对。后来发现是数据源的问题白折腾两小时。所以测之前一定先打乱或者校验一下数据的分布。6.3 堆排序建堆没生效症状是排序结果大体有序但局部乱或者末尾几个元素位置不对。先检查建堆的循环是不是range(n // 2 - 1, -1, -1)——注意是-1结尾很多人写成range(n // 2 - 1, 0, -1)漏掉了下标 0 那个根节点。根节点不处理最大元素就不在堆顶整个排序的根基就错了。第二个检查点是sift_down的end参数。建堆阶段传的是n - 1排序阶段每次传的是end - 1。这两个值搞混了会有两个后果要么下沉越界访问要么下沉范围大了把已经排好的元素又搅乱了。6.4 常见问题速查表症状最可能的原因快速验证递归深度异常大基准选到了极值三数取中没生效打印最大递归深度看是否接近 n数组越界分区指针没加边界检查用长度 2 和 3 的数组测无限循环分区时相等元素既不移也不换检查循环里的i 1分支排序结果少了元素两个递归区间没覆盖全校验[lo, p]和[p1, hi]的并集堆排结果末尾错乱建堆起点写成n // 2或漏了根打印建堆后的数组确认a[0]是最大值冒泡优化后结果错边界变量end更新时机不对用只有前 3 个元素乱序的数组测大数据下进程崩溃递归栈溢出换成尾递归或显式栈版本6.5 几条踩出来的经验最后分享几个我自己踩出来的点都属于文档上不会写、但实际会恶心你半天的类型。第一交换条件用严格大小比较。不管是冒泡的、插入的、还是堆下沉里的只要涉及「相等时不动」的语义就必须是严格比较。一旦写成稳定性直接没了而且很多时候结果还是对的你根本发现不了直到某天业务方告诉你「同样的订单两次排序出来的顺序不一样」。第二写排序一定先测小数组全排列。长度 4 或 5 的数组全排列也就几十上百种情况跑一遍全过基本可以确认逻辑正确。这比拿大数组瞎试效率高得多也是我现在的标准动作。第三复杂度表只能做初筛不能做决策。堆排和快排理论复杂度一样实测差一倍多三路快排的理论复杂度和普通快排一样在重复数据上快 2.6 倍。真正选算法的时候拿你的真实数据跑一遍比背十张复杂度表都有用。第四别在生产代码里手写这些排序。标准库的排序实现是几十年工程优化的结果混合了多种策略和边界处理你手写的版本几乎不可能超过它。手写排序的价值在于理解思想、应对笔试面试、以及在极特殊场景下做定制比如按对象某个字段排序且要保持稳定性这时候你用sorted(key...)就够了也不用自己写。