分治算法：分而治之的智慧

分治算法，说白了就是四个字——分而治之。我刚开始学算法时，觉得这名字挺唬人，后来发现它其实就是一种「拆解问题」的思维方式。你想想看，遇到一个复杂的大问题，硬着头皮上往往效率很低。但如果你能把它拆成几个小问题，每个小问题再拆成更小的问题……直到每个小问题都能轻松解决，再把结果合并起来——这就是分治的核心。

我个人习惯把分治算法比作「团队协作」：你一个人干不完的活，交给几个小组去干，每个小组再细分任务，最后汇总成果。嗯，这个比喻虽然简单，但很贴切。

分治思想的三步曲

分治算法通常包含三个步骤，我总结为：

  1. 分解（Divide）：将原问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题。
  2. 解决（Conquer）：若子问题规模较小而容易解决，则直接解决；否则递归地解决各子问题。
  3. 合并（Combine）：将各子问题的解合并为原问题的解。

关键点：分治算法的效率取决于「分解」和「合并」的代价。如果分解和合并的代价太高，分治可能还不如暴力解法。我在项目中就踩过这个坑——后面会讲。

为了让你更直观地理解分治的流程，我画了一张图：

分治算法核心流程 原问题 分解 子问题1 子问题2 子问题3 递归分解 最小子问题 最小子问题 最小子问题 合并 最终结果 分解 → 递归解决 → 合并

归并排序（复习）

归并排序是分治思想最经典的例子。我记得大学时第一次手写归并排序，debug 到怀疑人生——递归的边界条件总是搞错。但一旦理解了它的分治逻辑，你会发现它其实很优雅。

归并排序的思路：

  • 分解：将数组从中间一分为二，递归地对左右两半进行排序。
  • 解决：当子数组长度为1时，自然有序。
  • 合并：将两个有序子数组合并成一个有序数组。

来看代码：

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

小技巧：计算 mid 时用 left + (right - left) / 2 而不是 (left + right) / 2，可以避免整数溢出。我在嵌入式开发中吃过这个亏——当时用16位单片机，数组一大就出 bug。

归并排序的时间复杂度是 O(n log n)，空间复杂度 O(n)。它稳定、高效，但需要额外空间。如果你在内存受限的嵌入式系统里用归并排序，嗯，要掂量一下。

最大子数组问题

这个问题很有意思：给定一个整数数组，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。

举个例子：[-2, 1, -3, 4, -1, 2, 1, -5, 4]，最大子数组是 [4, -1, 2, 1]，和为 6。

用分治怎么解？

把数组从中间分成两半。最大子数组可能出现在三种位置：

  1. 完全在左半部分
  2. 完全在右半部分
  3. 跨越中点

前两种情况递归解决。第三种情况需要从中间向两边扩展，找到包含中点的最大子数组。

// 跨越中点的最大子数组
int maxCrossingSum(int arr[], int left, int mid, int right) {
    int sum = 0;
    int leftSum = -2147483648; // INT_MIN
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) leftSum = sum;
    }
    
    sum = 0;
    int rightSum = -2147483648;
    for (int j = mid + 1; j <= right; j++) {
        sum += arr[j];
        if (sum > rightSum) rightSum = sum;
    }
    
    return leftSum + rightSum;
}

// 分治求解最大子数组
int maxSubArraySum(int arr[], int left, int right) {
    if (left == right) return arr[left];
    
    int mid = left + (right - left) / 2;
    int leftMax = maxSubArraySum(arr, left, mid);
    int rightMax = maxSubArraySum(arr, mid + 1, right);
    int crossMax = maxCrossingSum(arr, left, mid, right);
    
    // 返回三者中的最大值
    if (leftMax >= rightMax && leftMax >= crossMax) return leftMax;
    if (rightMax >= leftMax && rightMax >= crossMax) return rightMax;
    return crossMax;
}

注意：分治解法的时间复杂度是 O(n log n)。但这个问题其实有 O(n) 的 Kadane 算法（动态规划）。我个人建议：面试时先讲分治思路展示你的算法思维，再提 Kadane 算法展示你的知识广度。

我曾经在一个金融项目中用分治算法处理股票收益的最大子数组问题。数据量不大，分治完全够用。但如果数据量上亿，我会毫不犹豫用 Kadane——省内存、速度快。

最近点对问题

这是分治算法中比较「烧脑」的一个。问题描述：给定平面上的 n 个点，找出距离最近的两个点。

暴力解法是 O(n²)，两两比较。n 很大时，这显然不行。分治算法可以做到 O(n log n)。

思路是这样的：

  1. 按 x 坐标排序所有点。
  2. 找到中位线，将点集分成左右两半。
  3. 递归求解左右两半的最小距离 d。
  4. 关键步骤：检查跨越中线的点对。只有 x 坐标差小于 d 的点才需要检查。
  5. 在「带状区域」内，按 y 坐标排序，每个点只需检查与其 y 坐标差小于 d 的后续几个点。

为什么只需要检查常数个点？因为在一个 d×2d 的矩形内，最多只能有常数个点，否则左右两半的最小距离就不可能是 d。这个证明有点绕，但结论很实用。

// 点结构
typedef struct {
    double x, y;
} Point;

// 按 x 坐标排序的比较函数
int compareX(const void* a, const void* b) {
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->x - p2->x) > 0 ? 1 : -1;
}

// 按 y 坐标排序的比较函数
int compareY(const void* a, const void* b) {
    Point *p1 = (Point *)a, *p2 = (Point *)b;
    return (p1->y - p2->y) > 0 ? 1 : -1;
}

// 计算两点距离
double dist(Point p1, Point p2) {
    double dx = p1.x - p2.x;
    double dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

// 暴力求解小规模点集
double bruteForce(Point P[], int n) {
    double min = 1e9;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (dist(P[i], P[j]) < min)
                min = dist(P[i], P[j]);
    return min;
}

// 分治求解最近点对
double closestUtil(Point Px[], Point Py[], int n) {
    if (n <= 3) return bruteForce(Px, n);
    
    int mid = n / 2;
    Point midPoint = Px[mid];
    
    // 分割点集
    Point Pyl[mid], Pyr[n-mid];
    int li = 0, ri = 0;
    for (int i = 0; i < n; i++) {
        if (Py[i].x <= midPoint.x && li < mid)
            Pyl[li++] = Py[i];
        else
            Pyr[ri++] = Py[i];
    }
    
    double dl = closestUtil(Px, Pyl, mid);
    double dr = closestUtil(Px + mid, Pyr, n - mid);
    double d = (dl < dr) ? dl : dr;
    
    // 构建带状区域
    Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++)
        if (fabs(Py[i].x - midPoint.x) < d)
            strip[j++] = Py[i];
    
    // 在带状区域内检查
    double min = d;
    for (int i = 0; i < j; i++)
        for (int k = i+1; k < j && (strip[k].y - strip[i].y) < min; k++)
            if (dist(strip[i], strip[k]) < min)
                min = dist(strip[i], strip[k]);
    
    return min;
}

// 主函数
double closest(Point P[], int n) {
    Point Px[n], Py[n];
    for (int i = 0; i < n; i++) {
        Px[i] = P[i];
        Py[i] = P[i];
    }
    qsort(Px, n, sizeof(Point), compareX);
    qsort(Py, n, sizeof(Point), compareY);
    return closestUtil(Px, Py, n);
}

避坑指南：我曾经在实现最近点对时，忘记在递归前对 Py 数组进行分割，导致带状区域检查时点集混乱，结果一直不对。调试了两天才发现——嗯，从那以后我每次写分治都会仔细检查「分解」这一步是否真的把数据分干净了。

最近点对问题的分治实现，最容易被忽略的是「按 y 排序的数组也需要分割」。很多教材只讲思路，不讲这个细节。但实际编码时，这个细节决定了你的程序能不能跑出正确结果。

分治算法的适用场景

不是所有问题都适合用分治。我总结了几条判断标准：

适合分治的特征 不适合分治的特征
子问题相互独立 子问题有重叠（此时用动态规划更好）
分解和合并的代价可控 分解或合并的代价接近 O(n²)
问题规模可以均匀分割 问题规模无法有效分割
递归深度不会导致栈溢出 递归深度过大（嵌入式环境尤其要注意）

举个例子：斐波那契数列用分治（递归）就是灾难——大量重复计算。但归并排序用分治就非常合适，因为子问题完全独立。

好了，这一章的内容就到这里。分治算法的核心就是「分而治之」——把大问题拆成小问题，小问题再拆成更小的问题，直到能直接解决，然后合并结果。归并排序、最大子数组、最近点对，这三个问题从易到难，覆盖了分治的典型应用场景。

代码写多了你会发现，分治不仅仅是一种算法，更是一种思维方式。遇到复杂问题时，不妨问问自己：这个问题能不能拆？拆了之后好解决吗？合并起来容易吗？想清楚这三问，分治就能为你所用。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →