午后两点，城市图书馆的借阅室一片狼藉——一万本图书散落在推车上，管理员小林要按书名字母顺序把它们全部归位。她望着面前的书山，深吸一口气：整理全部一万本确实令人头大，但如果是让五位图书管理员分工整理五个书架，每个书架只负责两千本呢？分而治之，先拆散，再逐层治理，这就是计算机科学里最优雅的策略之一——分治算法。本篇文章的主角，快速排序与归并排序，正是分治思想在排序领域的两颗明珠，从图书馆的书架到顶级互联网公司的海量数据，它们在背后默默指挥着亿万次有条不紊的“整理动作”。

岗位关联

理解分治排序不仅是面试的敲门砖，更是你设计高效算法的思维底色，掌握它，你将学会把庞大混乱的难题，拆解成优雅有序的解法。

目录
  1. 可视化演示
  2. 分治思想起源
  3. 快速排序原理
  4. 随机化快排
  5. 归并排序合并
  6. 稳定性对比
  7. 复杂度对比
  8. 最坏情况优化
  9. 场景与选型
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

快速排序和归并排序是基于分治思想的高效排序算法，平均时间复杂度O(n log n)。本文讲解快速排序的分区策略... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

分治思想与排：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

分治思想起源

小林的图书馆里，馆长下达了死命令：三天内将一万本书全部按书名排序上架。一万本！小林盯着书堆，觉得这比自己活过的日子还多。但经验丰富的老馆员陈叔走过来，指着墙上的楼层分布图说：“我们不需要一次处理一万本。把书按字母区间分成十堆，你负责 A–F，我负责 G–M，小张负责 N–R……每堆最多一千本，然后再把十个书架按顺序接起来，不就成了？”小林恍然大悟——这就是分治思想：一个庞大到无从下手的任务，拆成若干个独立的小任务，各自解决后再把结果拼接回完整答案。

计算机科学中的分治算法正是这样的“图书馆楼层分配方案”。它有三个固定步骤：分解（Divide）——将原问题递归分成规模更小的子问题；治理（Conquer）——子问题小到可以直接解决；合并（Combine）——将子问题的解组合成原问题的解。排序领域里，快速排序和归并排序是这个三招套路的杰出弟子，它们都把“排好一万本”拆成“排好两千本”，再拆成“排好四百本”，直到每堆只剩一本书——一本书当然是有序的。

这个递推式展开后，每一层都要处理 n 个元素，一共有 $\log_2 n$ 层，所以总工作量就是 O(n log n)。小林后来发现，陈叔这个“分区分配”的策略，正是计算机里递归的雏形——领导把任务拆下去，基层把结果报上来，每一层都在做同样的三件事。

T(n)=2T(n2)+O(n)\displaystyle T(n) = 2T\left(\frac{n}{2}\right) + O(n)
这个递推式描述分治排序的总工作量：把 n 个元素的问题拆成两个 n/2 的子问题，再花 O(n) 时间把结果合并，最终求解得到 O(n log n) 的时间复杂度。
  1. 递推的骨架$T(n)$ 表示处理 n 个元素所需时间，它由 “两个规模为 n/2 的子问题” 加上 “一次合并的开销” 构成。
    T(n)=2T(n2)+O(n)T(n) = 2T\left(\frac{n}{2}\right) + O(n)
  2. 拆解两次$2T(\frac{n}{2})$ 指分治把原任务一分为二，每个子任务规模减半，两个子任务都要独立完成。
    2×T(n2)2 \times T\left(\frac{n}{2}\right)
  3. 合并开销$O(n)$ 表示把两个有序半区拼成一个完整有序序列的线性代价——就像图书馆把两排已排序的书架首尾检查一遍。
    +O(n)+ \enspace O(n)

快速排序原理

第二天，小林在 F 书架前面犯了难：这一堆书有两百本，如果再用“按字母分区”的办法，她需要额外找一张大桌子来放临时分区。有没有办法不用额外空间就完成排序？这时她灵机一动：从书堆里随手抽出一本《三体》，以“S”这个字母为基准（枢轴），把书名首字母在 S 之前的书全放到左边，在 S 之后的全放到右边。经过一轮“分区”，《三体》自己就落在了它最终该在的位置上！接下来，左右两堆书各自重复这个过程，每一轮选一本新“基准书”，把更小的书放它左边、更大的放右边，直到每堆只剩一本。

快速排序的核心正是这个“抽基准书”的分区（partition）操作。算法流程清晰：从待排序区间选择一个元素作为枢轴（pivot）；然后遍历区间内所有元素，将小于等于枢轴的元素交换到左侧，大于枢轴的元素交换到右侧；这一步完成后，枢轴已经在整个数组的正确位置上，且左右两侧天然形成了两个待排序子区间——它们之间永远不需要再交换元素了。对左右子区间递归执行同样的分区，排序便像剥洋葱一样一层层完成。

小林发现，快速排序就像一个眼光独到的图书管理员：每次抽一本书出来做“标尺”，把书堆分成两半，然后对左右两半分别执行同样的套路。因为每一次分区都会把一个元素放到最终位置上，所以只要递归地做下去，不需要任何临时大桌子，整个书架就在原地被整理得井井有条。这也是它名字里“快速”二字的底气所在。

partition(A,l,r)⇒A[l..q−1]≤A[q]≤A[q+1..r]\displaystyle \text{partition}(A, l, r) \Rightarrow A[l..q-1] \le A[q] \le A[q+1..r]
分区操作的不变量：一趟扫描后，枢轴 A[q] 之前的元素都不大于它，之后的元素都不小于它，而 A[q] 的位置就是它在最终有序序列中的位置。
  1. 区间界定$A[l..r]$ 表示当前要排序的数组片段，$l$ 是左边界，$r$ 是右边界。
    partition(A,l,r)\text{partition}(A, l, r)
  2. 左区约束$A[l..q-1] \le A[q]$ 表示完成分区后，枢轴左侧的所有元素都不大于枢轴——相当于所有“S 之前的书”都堆在了《三体》左边。
    A[l..q−1]≤A[q]A[l..q-1] \le A[q]
  3. 右区约束$A[q] \le A[q+1..r]$ 表示枢轴右侧的所有元素都不小于枢轴——相当于“S 之后的书”都堆在右边。
    A[q]≤A[q+1..r]A[q] \le A[q+1..r]

随机化快排

可麻烦来了。小林发现，如果每次抽到的“基准书”恰好是当前书堆里书名最靠前的那一本，比如抽到《阿Q正传》，那么分区后左边空无一书，右边足足有 199 本——这哪里是分而治之，分明是把所有工作量都甩给了下一层！照这个运气，处理 n 本书要做 n 次分区，总共 O(n²) 次操作，跟最笨的冒泡排序一个档次，完全配不上“快速”的名号。小林意识到：枢轴选得好不好，直接决定快速排序的命运。

解决方案意外地朴素：既然无法预知哪本书适合做枢轴，那就从整堆书里随机抽一本。随机化快速排序在每次分区前，先从当前区间随机选择一个元素与最后一个元素交换，再以它为枢轴进行划分。这样一来，出现极端不平衡分区的概率被大大摊薄——虽然理论上仍可能抽到最坏情况，但对任何固定输入，算法的期望时间复杂度都是 O(n log n)，并且不依赖于输入数据的初始分布。

小林把“闭眼抽书”的策略推广到整个图书馆后，再也没遇到“分区全偏到一边”的尴尬。随机化并没有让算法在每次运行都最快，但它保证了平均而言几乎永远处于高效状态。就像老话说的：与其赌运气碰上一个好枢轴，不如把好运气均匀地分给每一个可能的枢轴。

E[T(n)]=1n∑i=0n−1(T(i)+T(n−i))+O(n)=O(nlog⁡n)\displaystyle \mathbb{E}[T(n)] = \frac{1}{n}\sum_{i=0}^{n-1}\left(T(i) + T(n-i)\right) + O(n) = O(n\log n)
随机化让选择的偏见消失：每个元素成为枢轴的概率均等，期望运行时间达到 O(n log n)，不再担心“恰好有序”这类魔鬼输入。
  1. 平均意义$\mathbb{E}[T(n)]$ 表示“随机选择枢轴”条件下处理 n 个元素的期望时间，是一种平均意义上的承诺。
    E[T(n)]\mathbb{E}[T(n)]
  2. 等概率加权$\frac{1}{n}\sum_{i=0}^{n-1}$ 表示每个位置成为枢轴的概率都是 1/n，把所有可能的划分方式按概率加权求和——因为随机抽书，每本书被抽中的机会均等。
    1n∑i=0n−1\frac{1}{n}\sum_{i=0}^{n-1}
  3. 左右两边递归$T(i) + T(n-i)$ 表示如果枢轴排在第 i 个位置，左右两区间分别要处理 i 和 n-i 个元素。
    T(i)+T(n−i)T(i) + T(n-i)
  4. 结果承诺$= O(n\log n)$ 是这个加权和的最终解，即随机化后算法的期望复杂度稳定在对数线性级别。
    =O(nlog⁡n)= O(n\log n)

归并排序合并

第三天的任务更难：馆长要求把所有书按作者姓氏稳定排列，也就是说，同一位作者的多本书，要按它们进馆的先后顺序排。小林试了试快速排序，发现它做不到——每次分区时，交换操作会把相同作者的书相对顺序打乱。一旁的陈叔笑了：“那就试试我的办法，先拆得碎碎的，再老老实实地合起来。”

归并排序的思路像一个严谨的档案馆管理员：先把整堆书从中间一分为二，递归地对左半堆和右半堆分别排序，最后将两个已经有序的半堆合并成一个完整的有序序列。合并动作使用双指针：两个指针分别指向两个半堆的起点，每次把较小的那本书放入结果数组，并前进对应指针，直到某一堆取完，再将另一堆剩余的书整体接在后面。因为两个半堆内部有序，合并时遇到相等元素总是先取左半堆的，所以相同作者的书会保持它们在原数组中的先后顺序——这就是稳定性的来源。

小林按照这个流程操作：先把 200 本书拆成两堆 100 本，两堆 50 本……直到每堆只剩一本，然后从最小的堆开始两两合并。整个过程没有“随机抽基准”的运气成分，每一轮合并都是踏踏实实的线性扫描，因此无论书怎么乱，归并排序一定在 O(n log n) 时间内完成。代价是她需要一张额外的长桌来摆放合并过程中的临时序列——这就是归并排序的空间开销 O(n)，拿空间换来了稳定和确定。

merge(L,R)={L+merge(L[1:],R)L[0]<R[0]R+merge(L,R[1:])otherwise\displaystyle \text{merge}(L, R) = \begin{cases} L + \text{merge}(L[1:], R) & L[0] < R[0] \\ R + \text{merge}(L, R[1:]) & \text{otherwise} \end{cases}
合并递归式：每次比较两个有序序列的头部，取出较小者，再递归合并剩余部分，最终得到一个完整有序序列。取左侧较小者时保持稳定。
  1. 基本情况判定$L[0] < R[0]$ 表示比较两个序列头元素，若左小则左头出列。
    L[0]<R[0]L[0] < R[0]
  2. 左头出列$L + \text{merge}(L[1:], R)$ 表示把左头元素放入结果，再对 L 去掉头部的剩余部分和完整 R 继续合并。
    L+merge(L[1:],R)L + \text{merge}(L[1:], R)
  3. 右头出列$R + \text{merge}(L, R[1:])$ 表示否则取右头元素，再对完整 L 和 R 去掉头部的剩余部分继续合并。
    R+merge(L,R[1:])R + \text{merge}(L, R[1:])

稳定性对比

小林现在面临一个选择难题：快速排序省空间但会打乱同作者书籍的相对顺序，归并排序稳定但需要额外空间。为了帮助她理解，陈叔做了一个小实验：取两本同作者的书，《呐喊》（上架编号 001）和《呐喊》（上架编号 002），在输入数组中它们一前一后。快速排序分区时，由于枢轴交换，编号 002 可能蹿到 001 前面；而归并排序合并时，遇到两本《呐喊》，双指针永远先取左半堆的 001，再取右半堆的 002，相对顺序纹丝不动。

稳定性（stability）是排序算法的重要性质：如果两个元素的排序键相等，排序后它们的相对顺序保持原样，则称该算法是稳定的。快速排序之所以不稳定，根源在分区操作中的“跨越式交换”——一个远在右侧的等值元素可能被交换到左侧等值元素之前。归并排序的稳定性则来自合并时“相等取左”的严格规则。在编程语言的内置排序中，Python 的 TimSort、Java 的对象数组排序都选择了稳定排序，正是因为现实场景（如按姓名排序后再按班级排序，希望保持第一次排序的相对顺序）频繁依赖这一点。

小林最终明白，稳定性和速度是两种不同维度的“品质”。快速排序就像一个手脚麻利但有点粗心的临时工，它能在原地快速完成任务，却可能打乱相同书籍的先后次序；归并排序则像慢工出细活的老员工，多占一张桌子但绝不乱序。实际工程里，是否需要稳定性往往成为选型的决胜因素，尤其是当待排序数据已经按某个次要键排过一次序时。

stability: ai=aj∧i<j⇒rank(ai)<rank(aj)(after sort)\text{stability: } a_i = a_j \wedge i < j \Rightarrow \text{rank}(a_i) < \text{rank}(a_j)(\text{after sort})
稳定性的数学界定：排序前位于前面的相等元素，排序后依然位于前面。若算法保证这一性质，即为稳定排序。
  1. 等值前提$a_i = a_j$ 表示两个元素的排序键相等，它们谁先谁后，单看键值无法区分。
    ai=aja_i = a_j
  2. 原始顺序$i < j$ 表示在输入数组中元素 $a_i$ 位于 $a_j$ 之前——像编号 001 的《呐喊》排在 002 前面。
    i<ji < j
  3. 排序后保序$\text{rank}(a_i) < \text{rank}(a_j)$ 表示排序后 $a_i$ 仍然排在 $a_j$ 前面，即相对顺序未被破坏。
    rank(ai)<rank(aj)\text{rank}(a_i) < \text{rank}(a_j)

复杂度对比

陈叔拿出一张手绘的表格，把两种算法的时间与空间开销放在一起对比。小林看到，在平均情况下，快速排序和归并排序的时间复杂度都是 O(n log n)，差别不大；但空间维度上，快速排序是“原地”算法，只需递归栈的 O(log n) 额外空间，而归并排序每次都开辟一个临时数组来合并，需要 O(n) 的额外空间。她想起昨天整理 F 书架时，快速排序就在书架本身上操作，而归并排序却把书拿到长桌上合并再放回来。

“所以没有免费的午餐。”陈叔总结道，“快排像在书架原地腾挪，省了桌子但怕遇到极端乱序；归并像搬到长桌上操作，多费空间但绝不出岔子。”小林点点头，她把这组复杂度对比记在笔记本上：如果数据量巨大且内存紧张，选择快速排序；如果稳定性和性能确定性更关键，归并排序是更稳妥的选择。

QuickSort:O(nlog⁡n)avg,  O(n2)worst,  O(log⁡n)spaceMergeSort:O(nlog⁡n)all cases,  O(n)space\begin{aligned} \text{QuickSort:} & \quad O(n\log n)_{\text{avg}},\; O(n^2)_{\text{worst}},\; O(\log n)_{\text{space}} \\ \text{MergeSort:} & \quad O(n\log n)_{\text{all cases}},\; O(n)_{\text{space}} \end{aligned}
复杂度总览：快排平均时间和归并排序相同，但快排最坏退化 O(n²) 且空间更省；归并排序任何情况都稳定在 O(n log n)，但牺牲 O(n) 额外空间。
  1. 快排三态$O(n\log n)_{\text{avg}}$ 表示平均情况下的时间开销，$O(n^2)_{\text{worst}}$ 表示极端不平衡分区时的最坏时间，$O(\log n)_{\text{space}}$ 是递归栈深度。
    QuickSort: O(nlog⁡n)avg,  O(n2)worst,  O(log⁡n)space\text{QuickSort: } O(n\log n)_{\text{avg}},\; O(n^2)_{\text{worst}},\; O(\log n)_{\text{space}}
  2. 归并恒定$O(n\log n)_{\text{all cases}}$ 表示无论输入如何，归并排序的时间开销都保持稳定，这是它的金字招牌。
    MergeSort: O(nlog⁡n)all cases\text{MergeSort: } O(n\log n)_{\text{all cases}}
  3. 空间花销$O(n)_{\text{space}}$ 表示归并排序需要与数据规模成正比的额外空间来存放合并结果。
    O(n)spaceO(n)_{\text{space}}

最坏情况优化

小林看着表格里的 O(n²) 陷入了沉思：哪怕用了随机化，快速排序在极端情况下仍然可能退化，比如当数据量巨大且恰好每次枢轴都选中位数（或最小）时，递归树会退化成一条长链。陈叔告诉她，工程实践中有几招专门用来“抢救”快速排序的最坏情况。第一招是三数取中（median-of-three）：从区间首、中、尾三个位置各取一个元素，以它们的中位数作为枢轴——这几乎不可能选到全局最小或最大，极大地避免了失衡分区；第二招是混合插入排序：当子区间长度小于某个阈值（如 10）时，改用插入排序直接完成，因为小区间上插入排序的常数开销远小于递归调用；第三招是尾递归优化：对递归过程中较大的子区间使用循环结构处理，从而将递归栈深度控制在 O(log n) 内，防止栈溢出。

这三招如同给快速排序上了三道保险：三数取中从源头把好枢轴关，插入排序给小区间提速，尾递归优化压低了调用栈的深度。小林在笔记本上写道：“优化不是花架子，而是针对已知弱点逐点设防。” 经过组合优化后的快速排序，在实际数据上几乎不会触发最坏情况，这也是为什么它成为多数通用排序库的底层默认选项。

pivot=median(A[l],  A[l+r2],  A[r])\displaystyle \text{pivot} = \text{median}\left(A[l],\; A\left[\frac{l+r}{2}\right],\; A[r]\right)
三数取中策略：取头、中、尾三个候选元素的中位数做枢轴，确保枢轴不是极端值，从而让分区尽量均匀。
  1. 三个候选$A[l],\; A[\frac{l+r}{2}],\; A[r]$ 分别是从左边界、中间位置、右边界取的三个元素，作为选枢轴的“选民”。
    A[l],  A[l+r2],  A[r]A[l],\; A\left[\frac{l+r}{2}\right],\; A[r]
  2. 取中位数$\text{median}(\cdot)$ 表示从三个候选中选出大小居中的那一个，这个值天然避开了最小和最大。
    pivot=median(… )\text{pivot} = \text{median}(\dots)
  3. 结果赋值将选出的中位数作为枢轴，再做标准分区，退化概率被大幅压低。
    pivot=…\text{pivot} = \ldots

场景与选型

最后一天，小林需要把整个图书馆的排序方案定下来。陈叔递给她一张决策清单：如果排序完全发生在内存中，数据量不大且内存紧张，首选快速排序——Java 的 Arrays.sort() 对基本类型就是这么做的；如果数据量大到放不进内存，需要借助磁盘分批排序，归并排序则是绝对的王者，它按块读入、排序、写回，再合并，这正是外部排序（external sorting）的标准玩法。稳定性同样关键：当需要按多个关键字依次排序时，使用稳定排序可以保证后一次排序不破坏前一次的顺序，这也是 Python sorted() 选择稳定算法的重要原因。

小林最终把方案拍板：内存内的日常图书借阅列表用快速排序，馆际互借的百万册备份数据用归并排序。两种算法殊途同归，都建立在“分而治之”这一条朴素智慧之上：把大问题拆到足够小，小问题就自然迎刃而解，而把解好的部分优雅地拼回去，就是整个算法最动人的一步。

decision={QuickSortmemory-limited, avg-case speedMergeSortstable required or external data\text{decision} = \begin{cases} \text{QuickSort} & \text{memory-limited, avg-case speed} \\ \text{MergeSort} & \text{stable required or external data} \end{cases}
选型决策规则：内存受限、追求平均速度时倾向快排；必须稳定或处理外部存储数据时选择归并排序。
  1. 快排条件$\text{memory-limited}$ 表示内存是瓶颈时，快速排序的原地特性能减少空间压力。
    QuickSortwhen memory-limited\text{QuickSort} \quad \text{when memory-limited}
  2. 归并条件$\text{stable required}$ 表示业务要求排序保持相等元素的原始顺序时，选择归并排序。
    MergeSortwhen stable required\text{MergeSort} \quad \text{when stable required}
  3. 外部数据$\text{external data}$ 表示排序数据无法完全载入内存时，归并排序天然支持分块读写，适合这类外部排序场景。

AI 应用场景

搜索引擎的文档排序

阶段：数据预处理与索引构建

解决的问题：搜索引擎每天需要抓取数亿网页并按键值排序建立倒排索引，传统冒泡或简单选择排序在百万级数据上耗时以小时计，无法满足索引天级更新的要求。采用归并排序后，可通过分块方式对海量网页URL排序，配合稳定的排序属性保证相同权重的文档相对顺序可预测。

具体案例：某电商搜索团队在构建商品索引时，先用归并排序按商品销量排序，再用另一键值（相关性分）做第二次稳定排序，从而让“销量较高”的商品在相关性相同时排在前面。

推荐系统的用户分层

阶段：特征排序与模型训练样本生成

解决的问题：推荐系统需要对海量用户按活跃度、消费能力等多维度打分并排序，数据量达到 TB 级且分布在多台机器上。使用快速排序的原地划分特性在单机内存内完成用户特征排序，结合三数取中优化，显著降低排序耗时。

具体案例：某短视频平台在晚间高峰前对 5000 万用户按实时活跃分排序，采用三数取中优化的快速排序，排序时长从 8 分钟压至 2 分钟，顺利赶在流量高峰前完成模型样本更新。

Python 演示

python56 行
import randomimport time def quick_sort(arr, left=0, right=None):    if right is None:        right = len(arr) - 1    if left >= right:        return    pivot = arr[right]    i = left - 1    for j in range(left, right):        if arr[j] <= pivot:            i += 1            arr[i], arr[j] = arr[j], arr[i]    arr[i + 1], arr[right] = arr[right], arr[i + 1]    mid = i + 1    quick_sort(arr, left, mid - 1)    quick_sort(arr, mid + 1, right) def merge_sort(arr):    if len(arr) <= 1:        return arr    mid = len(arr) // 2    left = merge_sort(arr[:mid])    right = merge_sort(arr[mid:])    merged = []    i = j = 0    while i < len(left) and j < len(right):        if left[i] <= right[j]:            merged.append(left[i])            i += 1        else:            merged.append(right[j])            j += 1    merged.extend(left[i:])    merged.extend(right[j:])    return merged def benchmark():    n = 10000    base = list(range(n))    random.shuffle(base)    arr1 = base[:]    arr2 = base[:]    t0 = time.time()    quick_sort(arr1)    t1 = time.time()    merge_sort(arr2)    t2 = time.time()    print("QuickSort time: %.4fs" % (t1 - t0))    print("MergeSort time: %.4fs" % (t2 - t1))    assert arr1 == sorted(base)    assert arr2 == sorted(base) if __name__ == "__main__":    benchmark()
目的：在 10000 个随机打乱的整数上分别运行快排与归并排序，输出两者耗时并验证排序正确性，直观对比两种分治排序的实际表现。
  1. pivot = arr[right]每次都取区间最后一个元素做枢轴，简单直接，是分区的基础。
  2. if arr[j] <= pivot:把小于等于枢轴的元素逐步交换到左侧，完成“左边小右边大”的划分。
  3. arr[i + 1], arr[right] = arr[right], arr[i + 1]把枢轴放到最终位置，此刻它已经不再需要移动。
  4. left = merge_sort(arr[:mid])递归排序左半段，体现了分治的“拆解”动作。
  5. while i < len(left) and j < len(right):双指针合并：每次比较左右头部，取较小者放入结果。
  6. merged.extend(left[i:])一方耗尽后，把另一方剩余的有序序列整体接上，完成合并。

常见误区

误区网上都说快排叫“快速”排序，那不管什么数据，它都应该比归并快吧？我直接无脑选快排就行了。

正解快排的“快”是平均意义上的快。在处理近乎有序的数据时，若没有随机化或三数取中优化，快排会退化到 O(n²)，远慢于稳定在 O(n log n) 的归并排序。就像小林抽基准书，如果总是抽中《阿Q正传》，分区就完全失衡。选型必须结合数据分布、稳定性需求和内存限制，不能只看名字。

为何常见：“快速”这个命名带有强烈的主观暗示，加上大多数教材展示的都是平均情况，初学者很容易把平均优势误当成绝对优势。

误区多开一个数组而已，反正现在内存都很大，O(n) 空间不算什么。

正解当数据规模达到千万级甚至亿级时，O(n) 意味着额外开辟与原始数据等大的内存，这可能导致内存翻倍甚至触发 OOM。归并排序每次合并都要创建临时数组，频繁分配与回收也带来额外开销。在实际的大数据排序场景（如外部排序），数据根本装不进内存，归并排序恰恰通过“分块读写+有序归并”在磁盘上解决问题，其空间代价是设计时无法回避的核心成本。

为何常见：算法课上测试数据只有几千个元素，空间差异不明显；但真实工业数据动辄 GB 级，O(n) 空间就变成了绕不开的瓶颈。

误区既然随机化能避免最坏情况，那随机化快排每次运行都应该比固定枢轴的快排更快。

正解随机化的作用是“摊薄”最坏情况出现的概率，让算法对任何输入都不再敏感，而不是让单次运行更快。它用一个随机数生成的额外耗时，换取了性能的确定性期望。实际中三数取中等启发式策略在多数场景下比纯随机更高效，因为随机数生成本身也有成本。小林后来发现，随机抽书虽然公平，但每次都“闭眼摸”也要花时间，不如先看头中尾三本书再定基准。

为何常见：人们常把“更安全”等同于“更快”，其实随机化解决的是方差问题，不是均值问题。

误区排序后值都一样，谁排前面不都一样吗？稳定不稳定有什么关系？

正解当元素只有一个排序键时，稳定性确实无关紧要；但当元素包含多个字段（比如先按班级排、再按学号排），稳定性就决定第二次排序能否保留第一次排序的顺序。例如先按“借阅次数”排序，再按“书名”排序，稳定排序能保证借阅次数相同的书之间保持书名字母序，而非稳定排序则会彻底打乱第一次排序的相对位置，导致两次排序的叠加效果失效。

为何常见：初学者在课本上接触的排序对象通常只是单个整数，看不出多键排序下稳定性的意义，因此天然低估它的价值。

面试题

Q1. 快速排序的核心思想是什么？

单选题 · easy

  • A.每次选出最大元素放到末尾
  • B.任选一个枢轴，将序列分为小于和大于枢轴的两部分，再递归排序← 正确答案
  • C.将序列两两比较后交换相邻元素
  • D.将序列分成两个子序列再交叉合并

答案：B。快速排序的本质是“选枢轴+分区+递归”：任选或按策略选一个枢轴，一趟分区后枢轴落在最终位置，左右两边递归执行同样流程。A 是选择排序的思路，C 是冒泡排序，D 更接近归并排序的描述。

Q2. 归并排序中“合并”两个有序数组的时间复杂度是？

单选题 · easy

  • A.O(1)
  • B.O(log n)
  • C.O(n)← 正确答案
  • D.O(n log n)

答案：C。合并两个有序数组时，双指针各自从头部扫描，每个元素被比较一次并放入结果数组，因此总操作与元素个数成正比，是线性时间 O(n)。O(n log n) 是整个归并排序的总复杂度而非单次合并。

Q3. 快速排序在什么情况下会退化到 O(n²)？

单选题 · mid

  • A.数据量超过 100 万
  • B.每次分区枢轴都恰好是当前区间的最小值或最大值← 正确答案
  • C.数据已经全部随机打乱
  • D.递归深度超过 log n

答案：B。当每次选取的枢轴都是区间的最值时，一侧没有元素，另一侧有 n-1 个元素，递归树退化成链表，比较次数逼近 n²/2。随机化或三数取中就是为了压低这种情况的发生概率。

Q4. 关于归并排序的稳定性，下列说法正确的是？

单选题 · mid

  • A.归并排序是不稳定排序，因为合并时会发生交换
  • B.归并排序是稳定排序，因为合并时相等元素总是先取左半部分← 正确答案
  • C.归并排序的稳定性取决于输入数据是否有序
  • D.归并排序的稳定性取决于枢轴的选择

答案：B。归并排序的稳定性来自合并规则的严格性：两个子序列头部元素相等时，取左子序列的元素。整个过程中没有跨距离的交换，所以相等元素的相对顺序得以保留。归并排序没有枢轴概念，稳定性与输入有序性无关。

Q5. 下列哪些策略可以优化快速排序的最坏情况？

多选题 · mid

  • A.三数取中选枢轴← 正确答案
  • B.子区间较小时改用插入排序← 正确答案
  • C.对所有子区间都用递归处理
  • D.对递归中较大子区间使用尾递归优化← 正确答案

答案：ABD。三数取中能避免枢轴取到极端值，混合插入排序减少小区间的递归开销，尾递归优化压低栈深度，这三者都是经典优化手段。C 选项“所有子区间都用递归”是普通实现，与优化无关。

Q6. 快速排序与归并排序在空间复杂度上的主要差异是？

单选题 · mid

  • A.快排是原地排序，额外空间 O(log n)；归并需要 O(n) 的额外数组← 正确答案
  • B.快排需要 O(n) 空间，归并是原地排序
  • C.两者都需要 O(n) 额外空间
  • D.两者都不需要额外空间

答案：A。快排在原数组上交换元素完成分区，递归栈深度平均 O(log n)；归并排序每次合并都要创建临时数组存放有序结果，累积需要 O(n) 额外空间。这一差异是选型时的关键权衡因素。

Q7. 在库函数如 Arrays.sort() 或 sorted() 的实现中，为什么有时选择归并排序而不是快速排序？

多选题 · mid

  • A.归并排序是稳定排序，能保留相等元素的原始顺序← 正确答案
  • B.归并排序在任何输入下都能保证 O(n log n)← 正确答案
  • C.归并排序不需要额外空间
  • D.归并排序在外部排序场景中天然支持分块处理← 正确答案

答案：ABD。库函数对对象排序时，稳定性是重要考量，归并排序天然稳定且不受输入分布影响；在数据量超过内存时，归并排序的分块思想也是外部排序的基础。归并排序需要 O(n) 额外空间，所以 C 错误。

Q8. 给定递推式 T(n) = 2T(n/2) + O(n)，其解是？

单选题 · hard

  • A.O(log n)
  • B.O(n)
  • C.O(n log n)← 正确答案
  • D.O(n²)

答案：C。该递推式对应分治排序的模式：拆成两个 n/2 的子问题，合并开销 O(n)。按主定理展开，递归树每层总工作量 O(n)，层数 log n，总复杂度 O(n log n)。这正是快排平均情况和归并排序所有情况的共同复杂度。

Q9. 关于“三数取中”选枢轴策略，以下说法正确的有？

多选题 · hard

  • A.从区间的首、中、尾取三个元素，用它们的中位数作枢轴← 正确答案
  • B.可以完全避免最坏情况 O(n²)
  • C.能显著降低选到最小或最大元素的概率← 正确答案
  • D.比随机化策略更差，没有任何优势

答案：AC。三数取中从三个位置取中位数，避免枢轴落在极端值上，从而让分区更均匀，C 正确；但它不提供数学上的“完全避免”，仍存在构造特殊输入使三数同为极端的情况，故 B 错误；D 显然错误，三数取中在实际中往往优于纯随机。

Q10. 外部排序（如对磁盘上的海量数据排序）通常选择哪种算法作为基础？

单选题 · hard

  • A.快速排序，因为它是原地排序
  • B.冒泡排序，因为实现最简单
  • C.归并排序，因为天然支持分块读入、排序、合并← 正确答案
  • D.插入排序，因为对小数据集高效

答案：C。外部排序的核心在于数据无法一次性载入内存，必须分成多个块，每块内部排序后写入磁盘，再通过多路归并得到整体有序结果。归并排序的分治合并结构正好匹配这一流程；快速排序的原地划分依赖随机访问完整数据，在磁盘场景下效率极低。