2026/9/7 5:41:35
FEATURED · 精选文章 
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 种语言的源码实现展示分治思想在经典问题求解与数据结构设计中的具体落地。什么是分治分与治两个阶段分治通常基于递归实现包含“分”和“治”两个步骤分划分阶段递归地将原问题分解为两个或多个子问题直至到达最小子问题时终止。治合并阶段从已知解的最小子问题开始从底至顶地将子问题的解进行合并从而构建出原问题的解。“归并排序”是分治策略的典型应用先将原数组递归划分为两个子数组直到子数组只剩一个元素最小子问题再从底至顶地合并有序子数组得到有序的原数组。仓库中的 Python 实现清晰对应了这两个阶段见 merge_sort.pydef 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 版 中找到对应结构。如何判断一个问题适合分治一个问题是否适合使用分治解决通常参考以下三个判断依据问题可以分解原问题可以分解成规模更小、类似的子问题且能够以相同方式递归地划分。子问题是独立的子问题之间没有重叠互不依赖可以独立解决。子问题的解可以合并原问题的解通过合并子问题的解得到。以归并排序为例逐条验证判断依据归并排序中的体现问题可以分解递归地将数组原问题划分为两个子数组子问题子问题是独立的每个子数组都可以独立地进行排序子问题的解可以合并两个有序子数组可以合并为一个有序数组值得注意的是并非所有分治问题都需要显式合并。以二分查找为例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(m1, 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)$ 的查找/插入性能本质上来自分治“每轮排除一半候选”的能力与 二分查找章节 的结论相互印证。小结分治的完整方法论可以归纳为四步判断适配性问题可递归分解、子问题相互独立、解可合并或无需合并选对划分方式固定中点归并排序、基准值快速排序、多划分点桶排序各有适用场景划分质量直接决定效率明确最小子问题递归必须有明确的终止条件如单元素子数组天然有序、$f(1)$ 单盘直接移动利用并发性独立子问题可分发到多核并行执行进一步压缩总运行时间。仓库在 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
hello-algo 中的分治算法：从归并排序到并行计算的效率跃迁
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 种语言的源码实现展示分治思想在经典问题求解与数据结构设计中的具体落地。什么是分治分与治两个阶段分治通常基于递归实现包含“分”和“治”两个步骤分划分阶段递归地将原问题分解为两个或多个子问题直至到达最小子问题时终止。治合并阶段从已知解的最小子问题开始从底至顶地将子问题的解进行合并从而构建出原问题的解。“归并排序”是分治策略的典型应用先将原数组递归划分为两个子数组直到子数组只剩一个元素最小子问题再从底至顶地合并有序子数组得到有序的原数组。仓库中的 Python 实现清晰对应了这两个阶段见 merge_sort.pydef 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 版 中找到对应结构。如何判断一个问题适合分治一个问题是否适合使用分治解决通常参考以下三个判断依据问题可以分解原问题可以分解成规模更小、类似的子问题且能够以相同方式递归地划分。子问题是独立的子问题之间没有重叠互不依赖可以独立解决。子问题的解可以合并原问题的解通过合并子问题的解得到。以归并排序为例逐条验证判断依据归并排序中的体现问题可以分解递归地将数组原问题划分为两个子数组子问题子问题是独立的每个子数组都可以独立地进行排序子问题的解可以合并两个有序子数组可以合并为一个有序数组值得注意的是并非所有分治问题都需要显式合并。以二分查找为例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(m1, 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)$ 的查找/插入性能本质上来自分治“每轮排除一半候选”的能力与 二分查找章节 的结论相互印证。小结分治的完整方法论可以归纳为四步判断适配性问题可递归分解、子问题相互独立、解可合并或无需合并选对划分方式固定中点归并排序、基准值快速排序、多划分点桶排序各有适用场景划分质量直接决定效率明确最小子问题递归必须有明确的终止条件如单元素子数组天然有序、$f(1)$ 单盘直接移动利用并发性独立子问题可分发到多核并行执行进一步压缩总运行时间。仓库在 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
