约 13 分钟4 张卡

分治算法

分治算法把一个问题拆成规模更小的同类子问题，分别求解，再将结果合并成原问题的答案。它的关键在于拆分后的结果是否足够：有些问题把左右答案相加就行，有些还需要在合并时处理跨越两边的关系。

归并排序可以用来理解这套结构。更进一步，在归并时统计逆序对，可以看到为什么子问题要同时返回“答案”和方便后续计算的状态。准备分治题时，需要能解释终止条件、合并为什么正确，以及整棵递归树的成本。

1. 面试核心

先记住这几条，再读正文

分治是一种问题组织方法，递归是一种实现方式。拆分必须让子问题变小，合并必须覆盖原问题中所有需要考虑的情况。卡 · 分解、求解与合并
子问题只返回局部答案可能不够。统计逆序对时，除了两边各自的数量，还要保留两边有序的状态，才能高效统计跨区间的逆序对。卡 · 三类逆序对
递归深度不是总时间。两路等分、每层合计线性工作得到 O(n log n)；只处理一路或长期不平衡的划分，会得到不同的递推式。卡 · 成本递推
空间看的是同时存活的辅助数据和调用栈。一份复用的归并数组占 O(n)，顺序执行左右子调用时，栈深度是 O(log n)。
分块排序再归并可以处理放不进内存的数据，但 MySQL 的 filesort 不一定落盘，也不代表总在使用同一种排序算法。卡 · 分解、求解与合并
外部排序要给输入块、归并缓冲、候选堆与运行时分别留内存；多轮归并会重复读写全量数据，临时磁盘和文件描述符也要预算。卡 · 综合题

2. 分解、求解与合并

卡 · 分治算法有哪些应用，怎样理解 MySQL filesort 中的分块排序与归并？

先为子问题定义一个明确的约定。例如处理半开区间 [lo, hi) 时，可以约定：“返回这段输入的统计结果，并将这段工作数组排好序。”这样父问题就知道，子调用返回后可以依赖哪些信息。

一个分治过程需要四个部分：

部分	需要明确的内容	归并中的例子
直接求解	哪些规模已经足够小	长度为 0 或 1，天然有序
分解	子问题范围、状态及是否严格变小	在 mid 处分成 `[lo, mid)`、`[mid, hi)`
求解	每个子问题返回什么、保证什么	分别得到有序的左右区间
合并	怎样形成父问题的完整结果	从两边开头取较小值，得到整体有序区间

这里的区间不是只能对半分。分治的拆分方式取决于问题，快速排序的两侧大小就由分区结果决定。关键是子问题可以被正确求解，并且所有分支都能走到直接求解的情况；递归终止的具体说明见递归。

“分开求解”也不要求代码同时运行。左右递归可以顺序执行；若改成并行，还要处理调度、同步和共享状态的成本。算法本身能拆分，不代表创建更多线程就一定更快。

2.1 子问题要保留哪些信息

合并需要的信息，决定子问题应该返回什么。 例如只知道左边有 2 个逆序对、右边有 1 个逆序对，仍然不知道跨越左右边界的逆序对有多少。若左右元素已经有序，跨边界的比较就可以批量完成。

这也是设计时应先想合并的原因：先问父问题拿到子结果后怎么得到答案，再反推子结果必须包含的状态。如果合并需要重新检查所有元素对，递归拆成两半并不会自动降低总复杂度。

分治与动态规划都利用子问题，但关注点不同。归并的左右区间基本不重复计算；如果相同状态反复出现，可以考虑存储结果来复用，见动态规划。不能只凭程序写成递归还是循环来区分它们。

3. 归并与逆序对

卡 · 归并时为什么可以一次加上左区间剩余长度来统计逆序对？

逆序对是满足 i < j 且 a[i] > a[j] 的一对下标。它描述原数组中前面的元素比后面的元素大；相等元素不构成逆序对。

例如 [2, 4, 1, 3, 5] 有 3 个逆序对，对应值为 (2,1)、(4,1)、(4,3)。直接枚举每一对下标需要 O(n²) 次比较，分治可以利用已经排好的两边减少重复比较。

3.1 三类逆序对

在 mid 处分开原区间后，每个逆序对恰好属于以下一类：

两个下标都在左边，由左子问题统计。
两个下标都在右边，由右子问题统计。
前一个下标在左边、后一个在右边，在合并时统计。

三类不会重叠，也覆盖了全部合法的下标对。左区间中的元素在原输入里都先于右区间，所以跨区间计数只需要判断值的大小。

假设左右已经分别有序，当前未合并部分的开头为 left[i] 和 right[j]。如果 left[i] > right[j]，左边从 i 开始剩下的元素都不小于 left[i]，因而都大于 right[j]。可以一次计入左边剩余的元素个数，不必逐个比较。

对 [2,4] 与 [1,3,5]：先取右边的 1，一次计入 2 个逆序对；取走左边的 2 后，再取右边的 3，计入剩下的 1 个。每次计数都绑定当前取走的右侧元素，因此不会重复计入同一对。

3.2 参考实现

下面的 Python 实现返回排序结果和逆序对数量。它先复制输入，递归操作工作数组 values，调用者传入的 nums 保持不变：

def sort_and_count(nums: list[int]) -> tuple[list[int], int]:
    values = list(nums)
    buffer = [0] * len(values)

    def solve(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = lo + (hi - lo) // 2
        count = solve(lo, mid) + solve(mid, hi)
        left, right, out = lo, mid, lo

        while left < mid and right < hi:
            if values[left] <= values[right]:
                buffer[out] = values[left]
                left += 1
            else:
                buffer[out] = values[right]
                count += mid - left
                right += 1
            out += 1

        while left < mid:
            buffer[out] = values[left]
            left += 1
            out += 1
        while right < hi:
            buffer[out] = values[right]
            right += 1
            out += 1
        for index in range(lo, hi):
            values[index] = buffer[index]
        return count

    count = solve(0, len(values))
    return values, count


nums = [2, 4, 1, 3, 5]
print(sort_and_count(nums))
print(nums)
print(sort_and_count([2, 2, 1]))

输出依次为 ([1, 2, 3, 4, 5], 3)、原输入 [2, 4, 1, 3, 5] 和 ([1, 2, 2], 2)。第二个例子中的两个 2 分别与 1 构成逆序对，两个 2 之间不构成逆序对。

solve(lo, hi) 返回时，values[lo:hi] 已经有序，返回值覆盖这段输入的所有逆序对。递归先建立左右有序的前提，合并再维护“buffer 已填部分有序、只消费过对应数量元素”的状态。左右区间都取完后，复制回工作数组，父调用就能继续依赖这个约定。

比较使用 <=，相等时先取左边，避免把相等元素算成逆序对。这里没有先对整个输入排序再计数，因为那样会丢失原始下标顺序。稳定排序等其他性质由排序统一说明。

4. 成本递推

卡 · 每次把问题分成两半，时间复杂度就一定是 O(n log n) 吗？

递推式把规模为 n 的问题成本，写成子问题成本与本层额外工作的和。本例的两个子问题大小分别为向下、向上取整的 n/2，合并和复制回工作数组都只遍历当前区间：

T(n) = T(floor(n/2)) + T(ceil(n/2)) + Θ(n)
T(0)、T(1) = Θ(1)

Θ(n) 表示这一层的工作与 n 同阶。对 n 为 2 的幂的情况，递归树第 0 层处理 n 个元素，第 1 层有两个 n/2，第 2 层有四个 n/4；每层合计仍是 n。共有 log₂n 层合并，所以时间是 O(n log n)。不是 2 的幂时，左右最多相差一个元素，仍得到同阶结果。

这种分析假设元素比较、下标和计数运算按常数成本计算。Python 整数可以增长到很大，若输入整数的位数也随问题规模增长，还需要计入大数比较和运算的成本。

4.1 相似写法为什么成本不同

递推形式	每层或每条路径的工作	时间
`T(n)=T(n/2)+Θ(1)`	只处理一半，当前层常数工作	Θ(log n)
`T(n)=2T(n/2)+Θ(n)`	两半都处理，每层合计线性工作	Θ(n log n)
`T(n)=T(n-1)+Θ(n)`	每轮只减少一个元素，仍遍历剩余区间	Θ(n²)
`T(n)=2T(n/2)+Θ(n²)`	当前合并本身要检查平方数量的关系	Θ(n²)

最后一行的各层成本是 n²、n²/2、n²/4……，总和仍为平方阶，不能因为递归深度是 log n，就再机械乘一个 log n。二分通常只继续处理一边，归并处理两边，二者同样把范围减半，但总工作不同。

4.2 辅助数组与栈

示例的工作数组 values 和复用数组 buffer 都是 O(n)，递归栈另占 O(log n)，总额外空间为 O(n)。两个子调用顺序执行，不会把整棵调用树的所有栈帧同时留在栈上。

每次递归都切出新的子列表，也会产生复制和分配成本。总分配量与某个时刻的峰值占用是不同指标，不能把每层分配的大小简单相加后当成峰值空间。这里用下标区间和一份复用数组，让这些成本更容易看清。

长度 n 的数组最多有 n(n-1)/2 个逆序对。使用固定宽度整数的语言时，要选择足够大的计数类型；例如 n=100000 时最大计数是 4999950000，已经超过 32 位有符号整数范围。

5. 分块排序的应用

卡 · 分治算法有哪些应用，怎样理解 MySQL filesort 中的分块排序与归并？卡 · 只有 256MB 内存，怎样排序 10GB 数据？

当全部数据无法同时放进内存，可以先把数据分成可处理的块，将每块排成有序段，再归并这些有序段。归并时只需维护各段当前待取的元素和读写缓冲，不需要一次装入所有记录；段数很多时，可以分多轮合并。

这个过程体现了“分别处理局部，再组合成整体”的思路，但磁盘读写量、合并路数和缓冲容量也影响成本，不能只拿内存算法的比较次数估计实际耗时。

MySQL 8.0 的 filesort 可以出现这种分块排序、落盘和归并过程。filesort 表示查询需要额外排序，不保证已经使用磁盘。 数据能放进排序缓冲时可以在内存完成；带 LIMIT 的某些查询还能采用优先队列等策略，不能把每次 filesort 都描述成完整的递归二路归并排序。执行计划中相应标记的含义见执行计划。

这里只用数据库排序说明应用方向。定位实际 SQL 的排序成本，还需要执行计划、数据规模与运行证据，不能由一个算法名称推定数据库一定走了哪条实现路径。

5.1 受限内存下的外部排序

外部排序是数据不能全部放入内存时，借助外部存储完成排序的方法。先把能放入内存的部分排成有序段，再读取各段当前最小的记录，逐步生成更大的有序段。

面对“10GB 数据、256MB 内存”这样的题目，先确认单位、记录格式、排序键和是否要求稳定。下面按 10 GiB 输入、256 MiB 进程内存预算、每条记录是八字节整数来计算；若输入是文本或变长对象，解析后的内存可能大于文件大小，要重新估计，不能照搬这个分块大小。

生成有序段时，先为输入块分配 128 MiB，其余内存留给缓冲、排序栈和运行时。 每次最多读入 128 MiB / 8 = 16,777,216 个整数，使用原地比较排序，再顺序写入一个临时文件。10 GiB / 128 MiB = 80，因此生成 80 个有序段。不能直接把 256 MiB 全部给数组，否则输入输出缓冲和其他对象会让进程超出预算。

多路归并是同时合并 k 个有序段。为每个输入段准备一个读取缓冲，并在最小堆中保存各段当前的第一条未输出记录。弹出最小值写入输出缓冲后，只从这条记录所属的段补入下一条；某段结束后，就从堆中移除这一路。堆最多有 k 项，每条记录的堆操作成本为 O(log k)，归并无需把所有段装入内存。

假设每轮最多 64 路，每路输入缓冲 1 MiB，输出缓冲 1 MiB，则显式读写缓冲共 65 MiB。堆还需保存 64 个候选及来源编号，文件对象、元数据、排序阶段仍存活的内存和运行时也要计入；不要在阶段切换时继续保留上一批大数组。实际路数还受文件描述符上限影响，64 路至少要同时打开 64 个输入文件和一个输出文件，并为进程其他文件留余量。

阶段	输入段数	处理方式	输出段数
生成有序段	原始文件	每次处理 128 MiB	80
第一轮归并	80	先合并 64 段，再合并剩下 16 段	2
第二轮归并	2	合并两个大段	1

一轮归并可以顺序处理多个组，65 MiB 是同时归并一组时的缓冲预算，不需要为全部 80 段同时分配缓冲。若允许更小的单路缓冲并且文件描述符足够，也可能一次合并 80 段，少一轮 I/O；代价是每路预读量减少，具体收益要结合存储设备测量，不能把“路数越多”直接当成“越快”。

假设不压缩、每条记录写出后仍为八字节，而且最终结果也落盘，生成段需要读、写各 10 GiB；两轮归并各再读、写 10 GiB，合计约 60 GiB 的逻辑 I/O。这个数不包含校验重读、文件系统元数据或故障重试，也不是磁盘设备实际传输量的保证。如果最后一轮直接把结果送给下游、不保存最终文件，可以少写一份结果，但输出的使用方式也随之改变。

临时空间必须单独预算。如果保留原始输入，并在一轮全部成功后才删除上一轮有序段，原始文件、旧段和新段会同时存在，峰值可能接近 30 GiB。每组合并成功就删除已经消费的段能降低峰值，但必须确保新输出完整可用，不能写到一半就删除唯一可恢复的输入。

验证时既要检查输出有序，也要检查记录数量和内容没有变化，还要检查空文件、最后一块不足整块、重复值、截断记录、I/O 失败和临时文件清理。小文件可以与内存排序结果逐项对照；大文件的摘要只能作为辅助检查，不能把摘要相同当成无碰撞的完整证明。进程峰值内存、打开文件数和临时空间应实测，但一次 RSS 样本没有超限，不代表所有输入与故障路径都满足硬内存上限。