
分治算法C算是我刷算法题和写底层工具里最稳的一类套路拆到不能再拆逐个击破最后拼回来。它不像动态规划那样需要设计状态也不像贪心那样要证明每一步局部最优只要你把“划分”和“合并”想明白代码基本不会跑偏。这篇文章我会从最基础的递归模型讲起覆盖归并排序、快速排序、最大子数组、快速幂再用平面最近点对作为完整实操案例把从设计到调试的过程走一遍。适合正在学算法的同学也适合那些会用sort但想理解sort背后发生了什么的人。我先说清楚分治不是银弹。它适合的问题是子问题互相独立、规模变小之后形式和原问题一致且合并代价不能太离谱。很多初学者把分治和递归混为一谈其实递归只是工具分治是一种组织计算过程的方式。同样用递归动态规划也能写递归但那是因为有重叠子问题需要记忆化分治则更强调子问题互不重叠。后面我会反复回到这个区别。1. 分治算法的本质与适用场景1.1 三板斧分解、解决、合并分治算法的英文 Divide and Conquer 说得很直白先分成小问题再征服它们。落实到 C 代码里就是一套固定动作分解Divide把原问题切成两个或多个规模更小的子问题子问题之间尽量避免重叠。解决Conquer对每个子问题递归调用自身。当规模小到某个阈值时直接返回结果。在递归里这个阈值就是递归边界通常写成if (left right) return;之类的一行。合并Combine把子问题的答案按一定规则整合成原问题的答案。很多同学会忽略第三步。比如归并排序里merge函数才是主角递归拆分只是把数组切小最大子数组问题里跨中点的答案需要单独扫一遍最近点对问题里合并阶段要额外检查中线附近的一窄条点。如果合并部分想不清楚分治代码写出来总是错的。我用一个生活化类比解释假设你要统计全校同学的身高分布最简单的方法是召集全校同学一个个量。分治方案是让每个班先统计出自己班的“身高最小值、最大值、平均身高”然后年级组长只需要合并各班统计结果最后校长再合并年级数据。每个班内部怎么做和校长无关。这就是子问题独立、合并规则清晰。1.2 什么样的题目适合用分治不是所有递归都能叫分治。判断一个问题适不适合分治我一般看三个条件子问题结构相同切出来的小问题必须是原问题的缩小版比如排序数组的子区间仍然是排序问题二叉树子树的最近公共祖先仍然是原问题的同型问题。如果切完问题性质变了递归就难写。子问题相互独立子问题之间不能有大量共享数据。如果切完后两个子问题都要读同一块数据并互相影响那叫重叠子问题更适合动态规划。合并代价可控合并阶段不能是 O(n²) 甚至更大否则整体复杂度会被合并拖垮。归并排序合并是 O(n)所以总体是 O(n log n)快速排序合并其实是 O(1)但 partition 在递归前就做了 O(n) 的划分。下面是我平时做的判断表问题特征适合分治更适合其他方法子问题规模变小且互相独立是否子问题大量重叠否动态规划合并逻辑复杂到无法描述否可能需要换思路小规模求解很简单是否问题结构天生是线性的可以先试二分/双指针也许贪心一个常见误区是看到“分成两半”就上分治。比如求数组前 K 大元素分成两半再各取前 K 大合并时还要排序复杂度不如直接nth_element。所以分治的核心不在“分”而在“合”。1.3 分治、递归、二分的关系这三者的关系我理了很多次才顺清楚。递归是一种编程手段函数调用自己本质是维护一个调用栈。二分查找虽然也用递归写法但它每次只处理一个子问题另一个子问题直接丢弃所以更准确地说是“减治”而不是“分治”。分治通常会把两个子问题的结果都拿回来做合并。举个例子二分查找在有序数组中找目标值只往左或往右走一条路不需要把两条路的答案拼起来。归并排序则必须拿到左半有序和右半有序再merge出完整有序数组。所以二分可以看成“只保留一个子问题的分治特例”但在判断复杂度和编写递归时它比标准分治简单一截。2. 经典分治场景的 C 实现与细节2.1 归并排序最标准的模板归并排序是理解分治的最好入口原因有三个合并规则直观、复杂度容易推导、代码边界少。标准实现如下void merge(vectorint a, int left, int mid, int right) { vectorint tmp; tmp.reserve(right - left 1); int i left, j mid 1; while (i mid j right) { if (a[i] a[j]) { tmp.push_back(a[i]); } else { tmp.push_back(a[j]); } } while (i mid) tmp.push_back(a[i]); while (j right) tmp.push_back(a[j]); for (int k 0; k (int)tmp.size(); k) { a[left k] tmp[k]; } } void mergeSort(vectorint a, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid 1, right); merge(a, left, mid, right); }几个值得注意的细节mid left (right - left) / 2比(left right) / 2更安全因为left right在大数组下标下可能溢出 int虽然现代 64 位环境中 int 溢出不常见但养成习惯没坏处。merge里用而不是这样相等元素会先取左半边的归并排序保持稳定性。用的话相等元素相对顺序会被打乱。临时数组每次在merge里创建简单但频繁分配内存。数据量大时可以在mergeSort外面准备一个全局或局部vectorint tmp(a.size())在merge里直接用索引写入。这是工程优化的第一步。归并排序的复杂度递推式是T(n) 2T(n/2) O(n)。解出来是O(n log n)。从直观上看每次递归都把区间折半递归深度是log n每一层所有合并加起来是O(n)所以总复杂度是O(n log n)。空间复杂度是O(n)因为临时数组和递归栈都是线性的。2.2 快速排序基准选择与 partition 的坑快速排序也是分治但它的工作顺序和归并反过来。归并是先递归后排好快排是先通过 partition 划分再对左右递归排好。我平时使用的是 Lomuto 分区方案代码短、好理解int partition(vectorint a, int left, int right) { int pivot a[right]; int i left; for (int j left; j right; j) { if (a[j] pivot) { swap(a[i], a[j]); i; } } swap(a[i], a[right]); return i; } void quickSort(vectorint a, int left, int right) { if (left right) return; // 随机化基准避免最坏情况 int pivotIndex left rand() % (right - left 1); swap(a[pivotIndex], a[right]); int pos partition(a, left, right); quickSort(a, left, pos - 1); quickSort(a, pos 1, right); }快排的复杂度很看基准选择。如果数组已经有序而每次基准都取最右端那么分区极度不均匀递归深度变成n复杂度退化成O(n²)。加上随机化后最坏情况在理论上仍然存在但概率小到可以忽略。C 标准库的std::sort不是简单快排它用的是内省排序递归到一定深度就转堆排序这是工程上的取舍。分区里另一个常见坑是相等元素处理。Lomuto 用把等于 pivot 的元素放到右边所以快排不稳定。如果你需要稳定排序就别用快排用归并。2.3 最大子数组问题跨中线从这里突破最大子数组问题是分治的经典练习。给定数组找连续一段元素和最大。暴力做法是枚举所有i,jO(n²)更优的线性做法是 Kadane 算法。但作为分治练习它展示了“答案可能横跨两个子问题”的情况。分治思路如下递归求左半最大子数组leftBest递归求右半最大子数组rightBest求“必须包含中间分割点附近”的跨中线最大子数组crossBest三者取最大值实现int maxCrossSum(vectorint a, int left, int mid, int right) { int sum 0; int leftSum INT_MIN; for (int i mid; i left; --i) { sum a[i]; leftSum max(leftSum, sum); } sum 0; int rightSum INT_MIN; for (int i mid 1; i right; i) { sum a[i]; rightSum max(rightSum, sum); } return leftSum rightSum; } int maxSubArraySum(vectorint a, int left, int right) { if (left right) return a[left]; int mid left (right - left) / 2; int leftBest maxSubArraySum(a, left, mid); int rightBest maxSubArraySum(a, mid 1, right); int crossBest maxCrossSum(a, left, mid, right); return max({leftBest, rightBest, crossBest}); }为什么跨中线最大子数组一定由 mid 向左的连续最大和加上向右的连续最大和拼成因为任意跨中线的子数组必然包含 mid 和 mid1 之间的连接部分所以可以从 mid 向两边扩展分别求出两侧最大后缀和最大前缀。这个例子的复杂度是T(n) 2T(n/2) O(n)也就是O(n log n)。虽然线性 Kadane 更优但通过分治代码你能直观感受到“合并阶段决定算法复杂度”这一句话的分量。2.4 快速幂数学计算里的减治变体快速幂严格说是“减治”因为每次只处理一个子问题然后直接利用结果但它在很多资料里被归入分治大类。实现思路计算x^n时如果n是偶数x^n (x^(n/2))^2如果n是奇数x^n x * (x^(n/2))^2这样递归深度是log n而不是n。long long quickPow(long long x, long long n, long long mod 1000000007) { if (n 0) return 1; long long half quickPow(x, n 1, mod); half half * half % mod; if (n 1) { return half * x % mod; } return half; }这里有个 C 特有的精度坑如果不取模half * half可能溢出long long。比如x 10^9平方就是10^18虽然没超过9.22e18但再乘一次就危险。所以做模运算时要手写安全乘法或者用__int128过渡。实际工程里我会写一个mulMod函数。快速幂的价值在于指数很大时对数级复杂度是从“暴力循环乘 n 次”到“分治翻倍”的质变。它也是后面很多组合数学、矩阵快速幂的基础。3. 实操过程用分治解决平面最近点对问题3.1 题目背景与暴力解法平面最近点对是我认为最能体现分治含金量的题目给你平面上n个点求任意两点之间的最小欧氏距离。暴力解是两两枚举复杂度O(n²)。当n 10^5时需要比较约10^10对点在普通机器上跑几十秒都算快的。如果题目还要求所有点不重复分治方案几乎是标准答案。先定义点结构struct Point { double x; double y; }; double calcDist(const Point a, const Point b) { double dx a.x - b.x; double dy a.y - b.y; return sqrt(dx * dx dy * dy); }暴力版本我一般写成double bruteForce(vectorPoint pts, int left, int right) { double best 1e100; for (int i left; i right; i) { for (int j i 1; j right; j) { best min(best, calcDist(pts[i], pts[j])); } } return best; }递归边界设为right - left 3因为点数少时暴力很快同时也保证后面合并阶段的格子证明有足够余量。3.2 分治设计排序、拆分、合并检查分治解法的主流程把点按 x 坐标升序排序。取中点mid把点集分成左右两半。递归求左半最近距离和右半最近距离取较小值为d。合并阶段把所有 x 坐标与中线距离小于d的点收集进strip数组。将strip按 y 坐标排序然后逐对检查距离如果小于d就更新。代码实现double closestPair(vectorPoint pts, int left, int right) { if (right - left 3) { return bruteForce(pts, left, right); } int mid left (right - left) / 2; double midX pts[mid].x; double d min(closestPair(pts, left, mid), closestPair(pts, mid 1, right)); vectorPoint strip; for (int i left; i right; i) { if (fabs(pts[i].x - midX) d) { strip.push_back(pts[i]); } } sort(strip.begin(), strip.end(), [](const Point a, const Point b) { return a.y b.y; }); for (int i 0; i (int)strip.size(); i) { for (int j i 1; j (int)strip.size() (strip[j].y - strip[i].y) d; j) { d min(d, calcDist(strip[i], strip[j])); } } return d; }外层调用前先按 x 排好序sort(pts.begin(), pts.end(), [](const Point a, const Point b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); double answer closestPair(pts, 0, (int)pts.size() - 1);3.3 合并阶段为什么只看中线附近的点这是最近点对分治证明里最微妙的一步。递归已经得到左右两侧各自的最近距离d如果存在一个更优的点对它一定一个点在左侧一个点在右侧因为两侧内部都已经检查过了。所以只需关注 x 坐标离中线midX小于d的点。如果点离中线超过d它和对面任意点的 x 方向差都超过d两点距离不可能小于d。更关键的是 y 方向剪枝strip按 y 排序后内部点对如果 y 坐标差已经不小于d距离必然不小于d可以直接跳过。经典证明是在一个d x 2d的矩形区域内最多只有常数个点因此每个点只需要和它后面若干个点比较这个常数通常被认为是 7 或 8。这也是合并阶段接近线性的原因。实现时注意用fabs(pts[i].x - midX) d而不是 d。取等号边界在浮点比较时容易出问题保守一点用小于。内层循环用strip[j].y - strip[i].y d作为终止条件因为strip已经按 y 排序后面的点 yy 差只会更大。3.4 复杂度分析与常数优化这个写法在合并阶段使用sort按 y 排序所以复杂度递推是T(n) 2T(n/2) O(n log n)解出来是O(n log² n)。如果希望达到严格O(n log n)需要在递归过程中保持一个按 y 排序的有序数组类似归并排序那样边合并边维护顺序。面试或竞赛中很多人的写法就是O(n log² n)因为n 10^5也能跑过代码更短。常数优化上我有三个经验最外层排序用sort后递归里不要每次都重新给整个点数组排序否则容易超时。比较距离时先用平方距离返回答案时再开根号。平方距离计算少一次sqrtsqrt很贵。strip每次都新建 vector 会频繁分配内存。可以先开一个全局临时数组每次只用索引范围填充。优化后的合并比较代码可以改成用平方距离double closestPairSquare(vectorPoint pts, int left, int right) { if (right - left 3) { double best 1e100; for (int i left; i right; i) { for (int j i 1; j right; j) { double dx pts[i].x - pts[j].x; double dy pts[i].y - pts[j].y; best min(best, dx * dx dy * dy); } } return best; } int mid left (right - left) / 2; double midX pts[mid].x; double d min(closestPairSquare(pts, left, mid), closestPairSquare(pts, mid 1, right)); vectorPoint strip; for (int i left; i right; i) { if (fabs(pts[i].x - midX) sqrt(d)) { strip.push_back(pts[i]); } } sort(strip.begin(), strip.end(), [](const Point a, const Point b) { return a.y b.y; }); for (int i 0; i (int)strip.size(); i) { for (int j i 1; j (int)strip.size() (strip[j].y - strip[i].y) * (strip[j].y - strip[i].y) d; j) { double dx strip[i].x - strip[j].x; double dy strip[i].y - strip[j].y; d min(d, dx * dx dy * dy); } } return d; }注意边界条件right - left 3保证至少有两个点。如果输入只有一个点题目通常会保证 n≥2否则函数可能返回1e100需要调用方自行处理。4. 常见问题、调试技巧与避坑清单4.1 高频翻车点我在本地实现这些分治算法时踩过的坑基本集中在几个固定位置问题典型原因解决办法递归不结束递归边界写错比如用left right但数组长度是偶数时永远不满足写成left right合并后数据丢失merge里临时数组下标从 0 开始写回时用a[left k]而不是a[k]仔细核对偏移快速排序死循环分区选到极端 pivot或者 partition 里i和j更新条件不对打印左右区间检查 partition 返回值是否可能等于left最近点对漏掉答案合并阶段没有检查跨中线点对或者strip过滤条件用了导致范围过大严格按 d过滤内层循环按 y 差值剪枝栈溢出递归深度达到n比如快排最坏情况使用随机化 pivot或改用迭代版本浮点误差sqrt后比较d导致边界抖动全程用平方距离最后开根号还有一个特别隐蔽的坑递归里把vectorPoint pts按值传递。整个点集在每层递归都被复制一遍复杂度直接多一个n数据稍大就会超时。正确做法是传递引用或者传下标区间。4.2 调试方法论小数据对拍、递归日志、断言调试分治算法我最推荐三个工具组合。第一个是小数据对拍。写一个暴力函数生成 n10 以内的随机输入跑分治版本和暴力版本比较结果。这里的“结果”可以是一个数也可以是整个有序数组。对拍代码一般在几十行内就能写完但价值极高。我上次调最近点对时就是靠对拍发现了strip过滤条件写错的问题。第二个是递归日志。在函数入口打印left、right、mid和关键变量。比如归并排序里发现某一段区间没有排好序就看是递归子问题没排好还是merge写回前临时数组没写好。日志不用多关键几行就行不然刷屏到看不清。第三个是断言。借助 C 的cassert在合并后检查不变量。归并排序合并后立即检查[left, right]是否单调不减最近点对递归返回前检查子区间最小距离是否大于等于 0。断言不满足会立刻中止程序定位速度比肉眼扫代码快得多。4.3 在实际开发中还要注意什么如果只是在竞赛题里写分治知道上面这些已经能应付大多数场景。但放到真实项目里还有几个容易被忽略的点。递归深度是 C 里最现实的问题。默认栈空间在 Linux 上通常只有 8MB一个递归函数如果每层占几百字节几十万层递归直接栈溢出。归并排序递归深度是log n安全但快速排序在不随机化时可能退化成n层。工程上处理大规模排序我直接用std::sort它内部是内省排序会在快排递归过深时切换成堆排序避免栈溢出。临时内存分配也是常见的性能杀手。归并排序的merge如果每次创建vector在千万级数据下内存分配次数让人崩溃。解决办法是复用一块缓冲区。最近点对的strip也一样可以复用全局数组只在递归里用下标标记范围。不要为了分治而分治。我在实际项目里见过有人用快速排序手写排序逻辑结果因为边界问题反复修 bug最后改成std::sort一行代码解决。分治是一种思维工具不是炫技工具。标准库已经优化的算法就放心用。4.4 面试和算法题里的分治模板如果你要应付面试或算法竞赛可以把下面这个模板刻在脑子里void solve(l, r) { if (l r || 规模足够小) { 直接求解; return; } mid l (r - l) / 2; solve(l, mid); solve(mid 1, r); // 合并逻辑可能跨 mid也可能像归并那样扫描 merge(l, mid, r); }然后判断复杂度时用主定理。分治通常写成T(n) aT(n/b) f(n)如果f(n)是多项式且n^log_b(a)增长更快则总复杂度是O(n^log_b(a))如果f(n)和n^log_b(a)同阶总复杂度是O(n^log_b(a) log n)如果f(n)增长更快总复杂度是O(f(n))归并排序里a2, b2, f(n)O(n)n^log_2(2)n同阶所以总复杂度是O(n log n)。这个模板能快速判断你设计的划分和合并是否合理避免写完代码才发现复杂度不对。我在实际写分治代码时最重要的一条经验是先把“合并”写清楚再来写递归骨架。很多人习惯先写递归底座再补合并结果递归逻辑没问题合并边界一改再改。反过来先明确合并函数接收什么参数、返回什么结果、怎么把两个子答案变成父答案递归代码会非常顺。分治的精髓从来不在“拆”而在“合”这一点在你做第一道真正的分治大题时就会深有体会。