企业官网建设流程全解析

分治算法这名字，乍一听像是只在教科书里出现的严肃术语。但你回想一下生活里天天在做的事情——收拾一堆乱糟糟的文件，先把合同、发票、笔记分成三堆，再将每一堆按时间排好，最后重新装进文件夹——这就是活生生的"分而治之"。拆开，搞定，再拼回去。绝大多数人其实早就用过这个思路，只是不知道它有个正式的名字叫分治。

我最早被分治算法触动，是学归并排序的时候。代码就十几行，可它每递归一层就把数组砍半，然后像梳头一样把两根有序序列并成一根，整个过程看得人直冒冷汗：递归到底层长什么样？合并的边界条件为什么这么写？后来刷题刷得多了才明白，分治不是一题一题的技巧，而是一种底层的思维范式。它的应用远不止排序——二分查找、快速幂、最大子数组、逆序对计数、大整数乘法、最近点对、线段树的区间查询，全都能从这套框架延伸出来。

这篇文章我打算换个讲法，不拿一堆概念砸你。核心思路放在前面，后面用四个完整案例把代码和原理焊在一起，最后聊聊我踩过的坑。每个案例我都会给出可以直接跑的代码、每一步的意图，以及当初让我自己困惑很久的细节。新手可以照着敲，有基础的朋友可以重点看第七、八节的边界和排查思路。这算是一份从"听过名字"到"能够动手写"的地图。

1. 分治算法的核心：拆开、搞定、拼回去

1.1 三个固定动作：分解、解决、合并

任何分治算法都跑不掉三个步骤。

第一步是分解，把一个规模为 n 的问题切成几个规模更小的子问题。判断切得好不好，关键看子问题是不是和原问题同构——也就是类型一样、只是规模缩小了，这样才能递归下去。

第二步是解决。递归地处理每个子问题。如果子问题已经小到可以直接给出答案，比如只剩一个元素、或者数组为空，那就返回，不再往下切。这个"递归基"是新手最容易写漏的地方，下面案例里你会反复看到它的身影。

第三步是合并。把子问题的解拼成原问题的解。这一步往往是整个算法最考验设计的地方，很多题目难不是难在分解，而是难在"怎么把两边的结果拼起来"。归并排序的合并需要双指针扫描两个有序数组，最大子数组问题则需要专门计算"跨过中线的子数组"，每一步都藏在合并逻辑里。

从代码结构上看，分治函数几乎长成一个样子：

def solve(problem): # 递归基：问题足够小，直接返回 if problem_is_trivial(problem): return direct_answer(problem) # 分解 left, right = split(problem) # 解决（递归） left_result = solve(left) right_result = solve(right) # 合并 return combine(left_result, right_result)

你拿这个模板去对照归并排序、快速排序、二分查找，会发现骨架完全一致。以后遇到一个分治题，先套这个模板把函数框架写出来，再往里填细节，心里会踏实很多。

1.2 哪些问题适合分治：两个必要条件

不是所有问题都能用分治硬切。判断一道题能不能用，我习惯先问自己两个问题。

第一，子问题是否共享了原问题的最优解？如果原问题的最优解可以由子问题的最优解直接组合出来，那说明它具有最优子结构。比如归并排序，整个数组排序的最优解，天然就是左半边排序加右半边排序再合并。

第二，子问题之间是否相互独立？如果它们互相纠缠，一个子问题的移动会改变另一个子问题的输入，那分治方案就掺水了。比如求解斐波那契数列，用分治切出 fib(n-1) 和 fib(n-2)，两者本身又是重叠的，递归树会指数爆炸。这种重叠子问题的情况更适合动态规划，而不是纯分治。

这两个条件像一对门神。最优子结构决定"能不能分"，独立性决定"分了值不值"。经典的快排、归并、二分查找全部通过，而斐波那契这种，分治虽然能写，但时间疯涨，属于典型的"可以但不划算"。

2. 看透复杂度：递归式、递归树与主定理

2.1 用递归式描述分治

分治算法的复杂度，用递归式描述最自然。设输入规模为 n，假如每次把问题切成 a 块，每块规模为 n/b，分解和合并的代价为 f(n)，那么总复杂度满足：

T(n) = a * T(n/b) + f(n)

这个式子读起来干巴巴，但它的信息量极大。归并排序每次切 2 块，每块减半，合并代价 O(n)，所以是 T(n) = 2 T(n/2) + O(n)。二分查找每次只递归一边，a = 1，每块减半，合并代价 O(1)，即 T(n) = T(n/2) + O(1)。

写递归式时注意一点：递归基的规模是多少。大多数人默认 T(1) = O(1)，这没问题，但做题算复杂度时，如果不把递归基附近的常数写出来，常见的数学归纳容易出错。我的习惯是显式写下 T(1) = O(1)，这样展开递归树时心里有底。

2.2 主定理怎么用

背递归式是一回事，真去展开递归树算复杂度又是另一回事。每次从根到叶子走 log_b n 层，每层要处理 a^k 个子问题，计算量来自所有层求和。这个过程可以用主定理压缩成三种情况，非常实用。

设 T(n) = aT(n/b) + f(n)，比较 f(n) 和 n^(log_b a) 的增长率，结果分成三档：

拿归并排序验证。a = 2，b = 2，n^(log_2 2) = n，f(n) = n，两者同阶，于是 T(n) = O(n log n)。二分查找 a = 1，b = 2，n^(log_2 1) = 1，f(n) = 1，同阶，复杂度 O(log n)。

主定理听起来高端，但它只是递归树的数学速算。如果你还没熟练到能一眼看出递归树长什么样，我的建议是动手画三级递归树：第一层 n，第二层两个 n/2，第三层四个 n/4，层数一共 log_2 n，每层合计工作量 O(n)，总工作量就是 O(n log n)。画到第三层你自然就信了，比背公式牢靠得多。

3. 实战一：归并排序，分治的标准模板

3.1 一双指针搞定合并

归并排序是理解分治最好的入门案例，因为它结构最标准：分解就是切一半，解决就是递归排序，合并就是把两个有序序列拧成一个有序序列。

def merge_sort(arr): if len(arr) <= 1: return arr[:] mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): i, j = 0, 0 result = [] while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # 剩余元素直接接上 result.extend(left[i:]) result.extend(right[j:]) return result

merge 函数是整个算法的胜负手。它依赖一个事实：left 和 right 本身已经升序。两个指针 i、j 一开始都在各自数组的头部，每次对比当前元素，谁小谁进结果数组，然后指针后移。这个操作总能在 O(len(left) + len(right)) 时间内完成，因为两个序列都是有序的，不需要回头比较已经被选中过的元素。

有个地方新手经常栽：while 循环跑完，其中一个数组可能还有残留。比如 left 全部取完了，right 还剩几个大的，直接 extend 上去就行。我第一次写的时候没想到要 extend，结果每次排序末尾莫名其妙少数字，排查半天才发现是合并结束时丢了尾巴。拿上面这段代码跑merge_sort([4, 2, 7, 1])，你手动模拟一遍就会明白为什么残留要用 extend 接上。

3.2 为什么归并排序一定稳定

判断排序算法是否稳定，看的是相等元素的相对顺序在排序前后是否被破坏。归并排序在合并时，用的是if left[i] <= right[j]，意味着当两边值相等时，优先取左边。这个细节决定了稳定性。

举例说明，两个数字 5a 和 5b，原序列是 [5a, 5b]，归并时 left 里是 5a，right 里是 5b，合并顺序会先取出 5a 再取 5b，于是排序后 5a 仍然排在 5b 前面。如果你把<=改成<，相等时优先取右边，稳定性立刻丢失。这是只改一个符号就会产生行为差异的典型场景。

归并排序的复杂度非常稳定，无论数组原本是升序、降序还是随机，时间都是 O(n log n)，空间 O(n)（因为要额外的 result 数组）。它的主要缺点也在这：一趟排序要申请临时数组，内存开销比原地排序大。实际工程里，如果内存紧张，或者数据量极大，更倾向快排。

4. 实战二：快速排序，谁快谁说了算

4.1 partition 是整个快排的灵魂

快速排序和归并排序的路径恰好相反：归并排序在"合并"阶段下足功夫，快速排序则在"分解"阶段狠下功夫。它的分解不是简单切一半，而是通过一次 partition 操作，让一个中心元素（叫 pivot）落到它最终该在的位置，同时让左边全部小于它，右边全部大于它。

def quick_sort(arr, low, high): if low >= high: return pivot_index = partition(arr, low, high) quick_sort(arr, low, pivot_index - 1) quick_sort(arr, pivot_index + 1, high) def partition(arr, low, high): # Lomuto 分区法，取最右元素做 pivot pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1

我重点讲讲 Lomuto 分区法。i维护的是"最后一个小于 pivot 的元素的位置"，j从头往尾部扫描。每发现一个小于 pivot 的值，就把它换到前面来，i跟着前进一格。扫描结束后，i + 1处就是 pivot 应该待的位置。整个过程读起来像是在玩推箱子：小的往左边推，大的不动，最后 pivot 归位。

分区的代价是 O(n)，但它将数组一分为二后，两个子问题不再相等。最理想的情况是每次分成一半一半，总复杂度 O(n log n)；最差情况如果每次 pivot 都是当前段的最小值或最大值，退化成每次切掉一个元素，复杂度掉到 O(n^2)。这也是快排名字里的"快"并不是绝对的，后面会展开讲。

4.2 快排不快的三个坑

第一，pivot 选择。Lomuto 每次取最右元素，如果输入恰好有序，每次 pivot 都是最大或最小值，快排直接变成冒泡级算法。工程上常用"三数取中"：取 low、mid、high 三个位置的中位数当 pivot，能有效对抗有序输入。

第二，递归深度。快排在分区极不平衡时，递归深度接近 n，调用栈会爆。归并排序深度恒为 log n，这一点快排比不过。后来一些库的排序实现干脆在递归深度超限时改用堆排序兜底。

第三，相等元素。前面的分区写法用的是< pivot才交换，等值时不动。大量重复元素会导致分区严重不平衡。想优化可以试试"三分分区"，把小于、等于、大于 pivot 的三类元素分别聚集，处理大量重复数据时效果好很多。

我自己的习惯是：数据量小(比如少于几十个元素)时快排未必有优势，很多框架源码里都会对小区间切到插入排序。这个优化是经验之谈，不必纠结，但知道它存在会让你写排序时更有分寸。

5. 实战三：最大子数组和，跨界才是真本事

5.1 跨过中线的"贯通子数组"

最大子数组问题是分治的一个经典应用：给定一个数组，找出连续子数组中和最大的那一个，返回和的值。这个问题用动态规划几乎三行写完，但用分治做一遍，你对"合并"阶段的认识会深一层。

def max_crossing_sum(nums, left, mid, right): left_sum = float('-inf') cur = 0 for i in range(mid, left - 1, -1): cur += nums[i] left_sum = max(left_sum, cur) right_sum = float('-inf') cur = 0 for j in range(mid + 1, right + 1): cur += nums[j] right_sum = max(right_sum, cur) return left_sum + right_sum def max_subarray(nums, left, right): if left == right: return nums[left] mid = (left + right) // 2 left_result = max_subarray(nums, left, mid) right_result = max_subarray(nums, mid + 1, right) cross_result = max_crossing_sum(nums, left, mid, right) return max(left_result, right_result, cross_result)

关键在第 37 行的max_crossing_sum。递归求解让我们拿到了左半边的最大子数组和右半边最大子数组，但真正的最大值可能横跨中线——一部分在左半边、一部分在右半边。这种情况下，你必须保证子数组紧紧贴着 mid 和 mid+1 这条分割线，否则它就不是"贯通"的。

计算左侧部分时，从 mid 往 left 方向累加，同时更新最大值；右侧从 mid+1 往 right 方向累加，同理。两侧最大和拼起来，就是横跨中线的最优贯通和。这个函数的时间是 O(n)，因为左右各扫一遍。

5.2 一个分治能做的，DP通常也能干

这里我想说点踩过坑之后的体会。不少分治题目，比如最大子数组、最长公共前缀、多数元素，都存在更简洁的线性扫描解法。那学分治还有意义吗？我认为有，原因有二。

第一，分治能帮你建立"跨合并点分析"的直觉。很多面试题表面上不是最大子数组，但核心步骤就是计算"某条分割线两侧的某种跨域贡献"，比如后面要讲到的逆序对。

第二，分治解法可以作为校验器。当你的动态规划解法出现了难查的边界条件时，写一个分治版跑随机测试数据对比结果，往往能快速定位 DP 状态转移错在哪。我在项目里处理类似问题时就干过这种"双算法对拍"，几分钟就能发现问题。

这个案例也说明分治不是性能上永远最优的方案，它是一种思想工具。而"递归+合并"的模板一旦熟练，遇到任何数值类问题，你都会自然地多问一句：能不能从中间劈开？

6. 实战四：逆序对计数，归并排序的隐藏技能

6.1 一边合并一边数逆序对

逆序对的定义是：下标 i < j 且 nums[i] > nums[j] 的一对数。暴力解法是双重循环 O(n^2)，n 到了十万级别就扛不住。分治解法巧妙地借用了归并排序的合并过程，在归并的同时统计逆序对，时间复杂度仍然 O(n log n)。

def merge_sort_count(arr, temp, left, right): if left >= right: return 0 mid = (left + right) // 2 count = 0 count += merge_sort_count(arr, temp, left, mid) count += merge_sort_count(arr, temp, mid + 1, right) i, j, k = left, mid + 1, left while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: # 右边元素比左边小，左半边从 i 到 mid 的所有元素都比 arr[j] 大 count += mid - i + 1 temp[k] = arr[j] j += 1 k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 for idx in range(left, right + 1): arr[idx] = temp[idx] return count

核心逻辑藏在else分支里。当 right 指针指向的arr[j]小于 left 指针的arr[i]时，说明arr[j]应该比左半边从i到mid的所有剩余元素都小。这些元素在原数组中的下标都比j小，但值都比arr[j]大，每一个都和arr[j]构成一个逆序对。数量恰是mid - i + 1。

这个"一次统计一片"的巧思，把逆序对计数从暴力 O(n^2) 优化到了 O(n log n)。我当年第一次看这个代码，卡在为什么是mid - i + 1而不是 1，后来手动模拟了一次才彻底悟了：每当你从右侧取一个元素，左侧剩余所有元素都等着和它配对，因为左侧这些元素在原数组里全部排在它前面。

6.2 注意逆序对会爆数量级

一个长度为 n 的数组，最多可以有 n(n-1)/2 个逆序对。n = 100000 时，最多接近 50 亿，远远超过 32 位整数的上限。我第一次用 C++ 写这道题时用了int，结果在大数据上报错，换成long long才过。用 Python 的朋友没这个问题，但换到其他语言时务必注意结果类型。

还有一点，这个算法会改变原数组顺序。如果你后续还需要原数组做别的事，记得提前存副本。逆序对计数的临时数组temp必须和原数组等长，且每次递归都在传递它，不要在递归函数里反复申请新数组，否则空间和时间都会变得很难看。

7. 二分查找为什么会翻车：边界条件的艺术

7.1 左闭右开和左闭右闭

二分查找是分治思想最精简的形态：每次把搜索区间切成两半，只保留可能包含目标值的那一半，a = 1，每层 O(1)。但很多人在它身上栽过跟头，问题几乎全出在边界条件上。

业界最主流的写法是"左闭右开"，区间表示为 [left, right)，初始 right = len(nums)。循环条件用while left < right，中间值取mid = (left + right) // 2。如果nums[mid] < target，说明答案在右半，left = mid + 1；否则答案在左半，right = mid。

def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left

这个函数返回的是第一个大于等于 target 的下标。之所以选左闭右开，是因为mid = (left + right) // 2在区间长度为 0 时才会跳出循环，循环体内mid始终有定义，而且区间收缩方向是明确的。如果你用"左闭右闭"，mid的判断和区间收缩方式完全不同，稍不留神就写出死循环。

7.2 找左边界、找右边界

二分查找的细节题，难在"找左边界"和"找右边界"的变体上。找右侧第一个大于 target 的位置，其实只要把lower_bound返回值 + 1，或者把比较条件反过来。找最右边等于 target 的位置，可以求"第一个大于 target 的下标"，再减 1。

我用一个表把常见需求串起来，方便你查：

二分查找的翻车，十有八九是忘记检查left越界。数组里所有元素都小于 target 时，lower_bound返回len(nums)，你再去nums[left]就直接报错。我的惯例是，调用二分的结果后，先写if idx < len(nums) and nums[idx] == target再使用。

8. 常见问题与排查技巧实录

8.1 递归栈溢出怎么办

分治天然和递归绑定，Python 默认递归深度大约 1000 层。归并排序和快排的递归深度是 log n 到 n 不等，当数组规模到百万级时，递归栈可能直接爆炸。我处理大规模数据时，常用三种办法。

第一种，手动增加递归限制，sys.setrecursionlimit()。这治标不治本，但用于练习或本地跑数据足够。

第二种，将递归改成显式栈的迭代写法。用列表模拟栈，把每次等待处理的区间入栈，循环处理直到栈空。这一招看起来不如递归优雅，但完全不受调用栈限制。

第三种，从算法侧釜底抽薪。如果数据规模太大且区间平衡性不能保证，就选择递归深度更稳定的算法，比如归并排序天然深度 log n，比快排更安全。我之前在某个批量任务里处理上亿条记录时，就是宁可多花点内存用归并的迭代版，也不赌快排的 pivot 运气。

8.2 代码写对了但结果不对，先查这三个地方

这类问题我遇到过太多次，分享三个最高频的排查点。

第一，递归基。检查函数最前面的终止条件是否覆盖了空输入和单元素输入。比如归并排序里len(arr) <= 1，少了等号，空数组会无限递归；逆序对计数里left >= right，少了等号会在单元素区间继续切分。

第二，合并时的索引范围。用数组区间形式的代码，合并循环里while i <= mid and j <= right是最容易写错的地方。漏了等号，mid 位置或 right 位置的元素就会被跳过。记住，闭区间里两个端点是包含在范围内的。

第三，临时数组的覆盖。很多递归实现里，临时数组和原数组的下标映射容易错位。合并结束前，必须把区间内所有数据拷贝回原数组，不是只拷贝部分。

我统计过自己写分治的 bug，七成以上出在"区间边界 +1 还是 -1"和"递归基是否覆盖空集"上。所以后来我的习惯是：写完代码，先跑三个用例——空数组、只有一个元素、两个元素，如果这三种情况都正常，再上大规模随机数据。

9. 我的一些实战心得

多说几句从实际项目里沉淀下来的东西。分治算法代码量不大，真正考验人的是"这个思路能不能迁移到别的场景"。我做过一个日志分析模块，日志散落在不同的时间段文件里，要先按时间分桶、再各自压缩、最后合并索引，本质上就是分治的落地方案。分段、独立处理、合并，这套逻辑不仅在算法题里有用，在系统设计里同样适用。

另外一个体会是，不要低估手动模拟的价值。遇到看不懂的递归代码，拿一张纸，写一个五六位的小数组，一层一层把递归展开、把变量值填进去，跑一遍之后，记忆会比任何讲解都深刻。这也是为什么我在上面的代码里反复加注释，而不是只用一句"你应该能看懂"带过。

最后提醒一句：分治不是银弹。子问题重叠的场景交给动态规划，子问题之间有顺序依赖的场景考虑贪心或拓扑排序，数据量极小时暴力可能反而更快。真正熟练的工程师，不是会背主定理，而是能判断这道题该不该走分治这条路，并且分完之后合并逻辑是什么。这篇的内容足够撑起你从零到上手，剩下的，靠刷题和写代码去巩固。