企业官网建设流程全解析

hello-algo 中的分治算法：从归并排序到并行计算的效率跃迁

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

分治（divide and conquer，分而治之）是一种基于递归、通过“分解—求解—合并”三步解决复杂问题的核心算法策略。本文以《Hello 算法》分治章节（divide_and_conquer.md）为主线，系统讲解分治的判断依据、它为何能提升算法效率（操作数量优化与并行计算优化），并结合仓库中 归并排序、快速排序、桶排序、汉诺塔 等 14 种语言的源码实现，展示分治思想在经典问题求解与数据结构设计中的具体落地。

什么是分治：分与治两个阶段

分治通常基于递归实现，包含“分”和“治”两个步骤：

1. 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
2. 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。

“归并排序”是分治策略的典型应用：先将原数组递归划分为两个子数组，直到子数组只剩一个元素（最小子问题），再从底至顶地合并有序子数组，得到有序的原数组。仓库中的 Python 实现清晰对应了这两个阶段，见 merge_sort.py：

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)

其中递归终止条件left >= right对应“最小子问题”（单元素子数组天然有序），merge()函数（merge_sort.py）通过双指针比较左右子数组元素、借助临时数组tmp合并，正是“治”的具体实现。同一实现还可在 Java 版 与 C++ 版 中找到对应结构。

如何判断一个问题适合分治

一个问题是否适合使用分治解决，通常参考以下三个判断依据：

1. 问题可以分解：原问题可以分解成规模更小、类似的子问题，且能够以相同方式递归地划分。
2. 子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
3. 子问题的解可以合并：原问题的解通过合并子问题的解得到。

以归并排序为例逐条验证：

值得注意的是，并非所有分治问题都需要显式合并。以二分查找为例（binary_search_recur.md），它每轮将搜索区间缩小一半，子问题之间同样独立，但“子问题的解无须合并”——找到目标元素时原问题同时被解决。其递归实现 binary_search_recur.py 中，dfs(nums, target, i, j)表示“在区间[i, j]中查找target”这一子问题，每一轮通过中点比较排除一半区间，体现了分治“每轮排除一半选项”的效率优势：

def dfs(nums: list[int], target: int, i: int, j: int) -> int: """二分查找：问题 f(i, j)""" # 若区间为空，代表无目标元素，则返回 -1 if i > j: return -1 # 计算中点索引 m m = (i + j) // 2 if nums[m] < target: # 递归子问题 f(m+1, j) return dfs(nums, target, m + 1, j) elif nums[m] > target: # 递归子问题 f(i, m-1) return dfs(nums, target, i, m - 1) else: # 找到目标元素，返回其索引 return m

通过分治提升效率：操作数量优化

分治不仅能解决算法问题，往往还能提升算法效率。在排序算法中，快速排序、归并排序、堆排序之所以快于选择、冒泡、插入排序，正是应用了分治策略。其底层逻辑可以从操作数量来推导。

以冒泡排序为例，处理长度为 $n$ 的数组需要 $O(n^2)$ 时间。若将数组从中点分为两个子数组：

• 划分需要 $O(n)$ 时间；
• 排序每个子数组需要 $O((n/2)^2)$ 时间；
• 合并两个子数组需要 $O(n)$ 时间。

总体时间复杂度为：

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

比较划分前后的操作总数：

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

这意味着当 $n > 4$ 时，划分后的操作数量更少，排序效率应该更高。需要强调的是：划分后的时间复杂度仍是平方阶 $O(n^2)$，只是常数项变小了——单次划分的收益有限。

关键在“递归地”划分：如果子数组不断从中点再划分，直至只剩一个元素时停止，这种思路就是归并排序，时间复杂度降为 $O(n \log n)$。这正是 merge_sort.py 中两层递归merge_sort(nums, left, mid)与merge_sort(nums, mid + 1, right)的数学本质：每层递归将问题规模减半（$\log n$ 层），每层合并总代价为 $O(n)$。

另一个方向是“多设几个划分点”：将原数组平均划分为 $k$ 个子数组，这与桶排序非常类似，适合排序海量数据，理论上时间复杂度可达 $O(n + k)$。仓库中 bucket_sort.py 的实现展示了这一划分过程：初始化 $k = n/2$ 个桶（预期每桶约 2 个元素），用i = int(num * k)将[0, 1)范围内的浮点数映射到桶索引，再逐桶排序、顺序取出合并：

# 初始化 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. 遍历桶合并结果

快速排序则是“划分点不固定”的分治变体。quick_sort.py 中partition()以nums[left]为基准数执行哨兵划分，将数组切分为“比基准小”与“比基准大”两个子区间，再对两侧递归；源码还提供了两种针对分治退化的工程优化：

• 中位基准数优化（QuickSortMedian）：取left/mid/right三个元素的中位数作为基准，避免最左元素恰好极值导致划分极度不平衡；
• 递归深度优化（QuickSortTailCall）：始终对较短的子数组递归、对较长的子数组改用循环，将最坏递归深度控制在 $O(\log n)$。

堆排序同样隐含分治式的“自顶向下堆化”过程：heap_sort.py 中sift_down()反复比较节点与其左右子节点并下移较大者，把根节点与末端元素交换后对缩减的堆重新堆化，直至有序。

通过分治提升效率：并行计算优化

分治生成的子问题相互独立，因此通常可以并行解决。也就是说，分治不仅可以降低算法的时间复杂度，还有利于操作系统的并行优化——在多核或多处理器环境中，系统可以同时处理多个子问题，更充分地利用计算资源，从而显著减少总体运行时间。

以桶排序为例，将海量数据平均分配到各个桶中后，所有桶的排序任务可以分散到各计算单元并行执行，完成后再合并结果。从源码结构看，bucket_sort.py 的第 2 步“对各个桶执行排序”中，每个桶的排序完全独立、互不依赖，天然适合作为并行任务单元；而冒泡/插入排序这类逐元素比较的串行算法则没有这种天然的并行边界。

分治的典型问题求解：以汉诺塔为例

分治能解决许多经典问题，文档中列举了：

• 寻找最近点对：先将点集分成两部分，分别找出各自部分的最近点对，最后找出跨越两部分的最近点对；
• 大整数乘法：如 Karatsuba 算法，将大整数乘法分解为若干较小整数的乘法和加法；
• 矩阵乘法：如 Strassen 算法，将大矩阵乘法分解为多个小矩阵的乘法和加法；
• 汉诺塔问题：通过递归解决，是典型的分治策略应用；
• 求解逆序对：借助归并排序的合并阶段统计逆序对数量。

仓库中对汉诺塔问题提供了多语言实现，Python 版 hanota.py 展示了标准的分治拆解：问题 $f(i)$（将src顶部的 $i$ 个圆盘借助buf移到tar）被拆为三个子问题——先把顶部 $i-1$ 个圆盘移到辅助柱、再移最大圆盘、最后把 $i-1$ 个圆盘移回目标柱：

def dfs(i: int, src: list[int], buf: list[int], tar: list[int]): """求解汉诺塔问题 f(i)""" # 若 src 只剩下一个圆盘，则直接将其移到 tar if i == 1: move(src, tar) return # 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf dfs(i - 1, src, tar, buf) # 子问题 f(1) ：将 src 剩余一个圆盘移到 tar move(src, tar) # 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar dfs(i - 1, buf, src, tar)

该实现满足分治三判据：问题按圆盘数量递归缩小、最小子问题 $f(1)$（单盘直接移动）有直接解、且三个子问题的执行序列恰好构成原问题的解。同章还提供了 递归求二分查找、快速幂 等相关分治问题，多语言代码位于 codes/python/chapter_divide_and_conquer/、codes/java/chapter_divide_and_conquer/ 等目录下。

分治在数据结构设计中的隐含应用

除了显式的经典问题，分治在算法与数据结构的设计中应用得非常广泛，文档将其概括为“润物细无声”的算法思想：

• 二分查找：将有序数组从中点索引处分为两部分，根据目标值与中间元素值的比较结果决定排除哪一半，并在剩余区间执行相同的二分操作（递归版见 codes/python/chapter_divide_and_conquer/binary_search_recur.py）；
• 归并排序 / 快速排序 / 桶排序：如前文所述，分别对应“固定中点划分 + 合并”“基准值划分 + 递归”“多划分点分桶 + 逐桶排序合并”三种分治形态；
• 树：二叉搜索树、AVL 树、红黑树、B 树、B+ 树等的查找、插入和删除操作都可视为分治策略的应用——每比较一次节点，搜索空间就缩小一半或按子树边界划分；
• 堆：堆是特殊的完全二叉树，其插入、删除和堆化操作隐含分治思想，heap_sort.py 中sift_down()的父子比较下移过程即是例证；
• 哈希表：虽不直接应用分治，但某些冲突解决方案间接体现了分治策略——例如链式地址中的长链表会被转化为红黑树以提升查询效率。

从时间复杂度角度看，这些结构 $O(\log n)$ 的查找/插入性能，本质上来自分治“每轮排除一半候选”的能力，与 二分查找章节 的结论相互印证。

小结

分治的完整方法论可以归纳为四步：

1. 判断适配性：问题可递归分解、子问题相互独立、解可合并（或无需合并）；
2. 选对划分方式：固定中点（归并排序）、基准值（快速排序）、多划分点（桶排序）各有适用场景，划分质量直接决定效率；
3. 明确最小子问题：递归必须有明确的终止条件，如单元素子数组天然有序、$f(1)$ 单盘直接移动；
4. 利用并发性：独立子问题可分发到多核并行执行，进一步压缩总运行时间。

仓库在 Python、Java、C++、C、C#、JavaScript、TypeScript、Go、Rust、Swift、Ruby、Kotlin、Dart、Dart 等语言下均提供了上述算法的对应实现与可运行示例，例如 codes/python/chapter_sorting/ 与 codes/go/chapter_sorting/，可直接运行验证各分治实现的行为，配合本章的 练习题 与 章节小结 可进一步巩固理解。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo