分治算法（Divide and Conquer）全面解析：判定准则、提效原理与典型应用

分治（divide and conquer，全称“分而治之”）是贯穿整个算法体系的最重要策略之一：它先把一个大问题拆成可独立求解的小问题，再自底向上合并子问题的解，从而“用递归换效率”。本文以《Hello 算法》分治算法章节（及其日文版）为主体，讲清三个判定准则、两条效率提升线索，并结合仓库内真实源码与对应实验代码，让读者既能“看懂分治”，也能“上手复现”。

一、什么是分治算法：两个阶段的递归展开

分治算法通常基于递归实现，整个求解过程可以被归纳为两个清晰的阶段：

1. 分（划分阶段）：递归地把原问题分解为两个或多个规模更小、结构相似的子问题，直到抵达规模最小的子问题为止——此时子问题的解是已知或平凡的；
2. 治（合并阶段）：从解已知的最小子问题出发，自底向上地把子问题的解逐步合并，最终构建出原问题的解。

其中英文单词 divide and conquer 本身就完整概括了这两层含义：divide（分割/分解）对应“分”，conquer（征服/治理）对应“治”。

“归并排序”是分治策略最典型的应用，可以逐字对照上面的定义：

1. 分：递归地将原数组（原问题）从中间划分为两个子数组（子问题），持续到子数组只剩下一个元素（最小子问题）；
2. 治：自底向上把有序的子数组（子问题的解）两两合并，最终得到整体有序的原数组（原问题的解）。

在仓库的 归并排序 Python 实现 中，这两个阶段在函数结构上一目了然：

def merge_sort(nums: list[int], left: int, right: int):
    """归并排序"""
    # 终止条件
    if left >= right:
        return  # 当子数组长度为 1 时终止递归
    # 划分阶段
    mid = (left + right) // 2          # 计算中点
    merge_sort(nums, left, mid)        # 递归处理左子数组
    merge_sort(nums, mid + 1, right)   # 递归处理右子数组
    # 合并阶段
    merge(nums, left, mid, right)

二、如何判断一个问题适合分治：三个判定准则

并不是所有问题都适合分治。某问题能否用分治高效求解，通常可参考下面三个判断依据：

1. 问题可以分解：原问题可以分解为规模更小、且类型相似的子问题，并且能够以相同方式递归地继续划分；
2. 子问题是独立的：子问题之间互不重叠、互不依赖，因此可以各自独立求解；
3. 子问题的解可以合并：原问题的解恰好可以由各子问题的解通过某种方式合并而来。

准则 2 尤其关键，它把分治和“共享重叠子问题”的思路（例如借助记忆化递归的解法）区别开来——子问题完全独立，才意味着可以重复使用同一套递归模式，也才意味着存在并行化的潜力。

显然，归并排序完全满足以上三条：

1. 问题可以分解：递归地把数组（原问题）划分为两个子数组（子问题）；
2. 子问题是独立的：每个子数组内部可以独立排序（子问题可以独立求解）；
3. 子问题的解可以合并：两个有序子数组（子问题的解）可以合并为一个整体有序的数组（原问题的解）。

满足这三条的例子在仓库中比皆是：例如 二分查找的递归实现 把一个查找区间 [0, n-1] 每次按中点拆成两个半区间、只继续处理其中包含目标值的一半；汉诺塔求解 把 n 个圆盘的移动拆成规模为 n-1 与 1 的两类子任务。它们共享同一个模式：拆分 → 递归求解 → 合并结果。

三、分治为什么能提升效率：两条底层逻辑

分治不仅能“解出”算法问题，更常常能“提速”算法——快速排序、归并排序、堆排序之所以普遍快于选择排序、冒泡排序、插入排序，正是因为它们应用了分治策略。那么底层逻辑是什么？将一个“大问题”拆成若干“子问题”，求解再合并，为何会优于“直接求解原问题”？可以从操作数量和并行计算两个视角来回答。

3.1 操作数量优化：把“一次排到底”改为“分层分治”

以冒泡排序为例：处理长度为 $n$ 的数组需要 $O(n^2)$ 时间。若按下面的做法，先把数组从中点一分为二：

• 划分本身需要 $O(n)$ 时间；
• 对两个规模各为 $n/2$ 的子数组排序，各需 $O((n/2)^2)$ 时间；
• 再把两个有序子数组合并为一个有序数组，需要 $O(n)$ 时间；

则总时间复杂度为：

$$O(n + (\frac{n}{2})^2 \times 2 + n) = O(\frac{n^2}{2} + 2n)$$

接着比较“划分前”与“划分后”的操作总量（不等式左边是直接冒泡排序，右边是一次划分 + 两个子数组各自冒泡 + 合并）：

$$\begin{aligned} n^2 & > \frac{n^2}{2} + 2n \newline n^2 - \frac{n^2}{2} - 2n & > 0 \newline n(n - 4) & > 0 \end{aligned}$$

结论是当 $n > 4$ 时，划分后的操作数量严格更少，排序效率更高。 但要特别注意：一次划分后时间复杂度依然是平方阶 $O(n^2)$，只是复杂度常数项变小了。各策略的操作量对比如下表所示：

处理方式	操作量级	渐近复杂度
直接对整个数组冒泡排序	$n^2$	$O(n^2)$
一次划分 + 两个子数组冒泡 + 合并	$\frac{n^2}{2} + 2n$	仍是 $O(n^2)$（常数项更小）
从中点不断划分至单元素，再自底向上合并	每层合并共 $O(n)$，共 $O(\log n)$ 层	$O(n \log n)$
多设置划分点，均分为 $k$ 个子问题	接近 $n + k$	理论 $O(n + k)$

顺着“继续划分”的思路进一步推导，会得到两个重要的推论：

1. 如果我们不断把子数组再从其中点一分为二，直到子数组只剩一个元素——这种思路实际上就是归并排序，其每层划分/合并合计 $O(n)$，递归深度为 $O(\log n)$，因此总时间复杂度为 $O(n\log n)$。合并步骤的正确实现可参考 merge_sort.py 中的 merge()：用临时数组按序归并两个有序子数组，再写回原区间，其算法行为与上文“治”的阶段完全吻合；
2. 如果我们多设置几个划分点，把原数组平均分成 $k$ 个子数组——这种情况与桶排序非常相似，它特别适合排序海量数据，理论时间复杂度可达 $O(n + k)$。

也就是说，分治提升操作效率的“源泉”，是把原本一次性完成的 $O(n^2)$ 量级操作，摊薄到 $\log$ 层乃至 $k$ 个可复用子问题的处理中，让每次比较/合并都在更小的规模上进行。

3.2 并行计算优化：独立子问题天然适合多核调度

分治生成的子问题相互独立，因此通常可以被并行求解。也就是说，分治不仅能降低算法的时间复杂度，还有利于操作系统的并行优化。

并行优化在多核或多处理器环境中尤为有效：当系统能够同时处理多个子问题时，计算资源得到更充分的利用，整体运行时间可以被显著压缩。

以图所示的“桶排序”为例：先将海量数据平均分配到各个桶，再让每个计算单元各自负责若干个桶内的排序任务，全部完成后合并各桶结果即可。

仓库中的 桶排序 Python 实现 虽然以单线程写出，但其函数结构本身就清晰标记了“分配 → 各桶排序 → 合并”三个可并行衔接的步骤：

def bucket_sort(nums: list[float]):
    """桶排序"""
    # 初始化 k = n/2 个桶，预期向每个桶分配 2 个元素
    k = len(nums) // 2
    buckets = [[] for _ in range(k)]
    # 1. 将数组元素分配到各个桶中
    for num in nums:
        i = int(num * k)          # 输入数据范围为 [0, 1)，映射到桶索引
        buckets[i].append(num)
    # 2. 对各个桶执行排序（桶之间互不影响，可交由不同计算单元并行）
    for bucket in buckets:
        bucket.sort()             # 也可替换成其它排序算法
    # 3. 遍历桶，合并结果
    i = 0
    for bucket in buckets:
        for num in bucket:
            nums[i] = num
            i += 1

其中第 2 步“各桶排序”彼此独立，正是分治并行化的最佳落点；第 1 步的数据分桶与第 3 步的顺序合并，则对应分治的“分”与“治”。

四、分治的典型应用：从经典算法到数据结构

分治的思想渗透在算法与数据结构设计的方方面面。

4.1 经典算法问题

• 寻找最近点对：先把点集划分为两部分，分别求出各部分内部的最近点对，最后再处理跨越两部分的最近点对，三者取最小；
• 大整数乘法：例如 Karatsuba 算法，把大整数乘法分解为若干次更小整数的乘法与加法；
• 矩阵乘法：例如 Strassen 算法，把大矩阵乘法分解为多个小矩阵的乘法与加法；
• 汉诺塔问题：递归天然可解，是分治策略的经典应用——仓库中的 hanota.py 将其递归地描述为三个子任务：借助目标柱把顶部 $i-1$ 个圆盘移到缓冲柱（$f(i-1)$）、把最底圆盘直接移到目标柱（$f(1)$）、再借助源柱把 $i-1$ 个圆盘从缓冲柱移到目标柱（$f(i-1)$）；
• 求解逆序对：若序列中某个位置靠前的数大于靠后的数，二者构成一个逆序对。该问题可借用归并排序的合并过程，在“治”的阶段统计跨区间逆序对数量。

4.2 算法与数据结构设计

• 二分查找：把有序数组按中点索引一分为二，根据目标值与中间元素的比较结果排除其中一半区间，在剩余区间重复同样的二分操作，可参考 二分查找实现；
• 归并排序：本文章节一已详述，不再重复；
• 快速排序：选定基准值后，把数组划分为“全部小于基准值”和“全部大于基准值”的两个子数组，再对两部分递归执行同样的划分，直到子数组只剩一个元素，实现见 quick_sort.py；
• 桶排序：把数据分散到多个桶，桶内各自排序后依次取出拼接为有序数组，实现见 bucket_sort.py；
• 树：二叉搜索树、AVL 树、红黑树、B 树、B+ 树等结构的查找、插入、删除操作都可以视为分治的应用——插入/删除时在左右子树间递归定位，删除后的旋转修复也只在局部子树内进行，参见仓库中的 二叉搜索树 与 AVL 树；
• 堆：堆是特殊的完全二叉树，插入、删除、堆化等操作的“自底向上/自顶向下”路径本质上都隐含分治思想，可参考 my_heap.py 中的上滤与下滤过程；
• 哈希表：哈希表本身并不直接应用分治，但若干哈希冲突解决策略间接用到了分治——例如链式地址法中，过长的链表会被转换为红黑树以提升查询效率，相关讨论见 hash_collision.md。

可以看到，分治是一种“润物细无声”的算法思想——它不一定被写在函数名里，却潜藏于各类算法与数据结构之内。

五、在 Hello 算法仓库中对照学习与动手验证

《Hello 算法》仓库为分治专题提供了同构的多语言代码树：除 Python 外，C、C++、Java、Go、Swift、Rust、Ruby、Kotlin、TypeScript、C#、Dart、Zig 等语言均有同名实现，目录组织一致，例如本章节的递归分治代码位于 codes/<语言>/chapter_divide_and_conquer/ 下（如 c 语言版、go 版），可以跨语言对照函数签名与递归结构。

为了把“分治只是抽象思想”落到可读、可运行的代码上，建议优先研读以下四组最小实现（均含可直接运行的 Driver Code）：

分治知识点	Python 实现	可对照的专题文档
“分 + 治”两阶段模板（归并排序）	chapter_sorting/merge_sort.py	归并排序
划分后规模减半的递归（二分查找）	chapter_divide_and_conquer/binary_search_recur.py	分治搜索策略
划分 + 合并 的三段式（汉诺塔）	chapter_divide_and_conquer/hanota.py	汉诺塔问题
分治建树（划分序列为左右子树）	chapter_divide_and_conquer/build_tree.py	构建二叉树问题

其中 binary_search_recur.py 把整个查找区间建模为“问题 $f(i,j)$”，通过比较中点元素把问题递归约简为子问题 $f(m+1,j)$ 或 $f(i,m-1)$——这是理解“分治 = 递归地把问题缩小”的最小样例；而 build_tree.py 演示了利用前序与中序遍历结果递归切分左右子树的建树过程，属于分治在二叉树上的直接应用。

动手验证时（以 Python 为例，需已安装 Python 3），可在仓库根目录执行：

cd codes/python
python3 chapter_sorting/merge_sort.py          # 观察分治排序输出
python3 chapter_divide_and_conquer/hanota.py   # 观察圆盘按分治策略移动
python3 chapter_divide_and_conquer/binary_search_recur.py  # 观察递归二分

每个文件末端的 if __name__ == "__main__": 都自带了构造好的测试数据与打印输出，可以直接看到分治过程的结果。

小结：把“大问题”交给递归，把“小问题”交给并行

分治算法用两句话即可概括：在“分”的阶段不断递归地缩小问题规模，在“治”的阶段自底向上合并子问题的解。要判断问题能否用分治，只需要反复问三个问题：能否分解？子问题是否独立？解能否合并？而它带来效率提升的根本原因，也无外乎两条：操作数量被摊薄到对数层级或 $k$ 个并行子任务中；独立子问题天然适配多核并行。读懂这四点，再去阅读仓库中归并排序、汉诺塔、递归二分等实现，你会发现那些看似不同的算法，其实共享着同一套“分而治之”的骨架。