中等C++7 分钟2,296 字

分治算法——大问题拆成小问题

你有没有遇到过这样的难题——桌上一堆乱糟糟的乐高零件,要拼出一个大城堡,不知道从哪下手?聪明的方法是:先按颜色分成几堆,每堆拼一个小部分,最后再把小部分组合起来。这就是分治​​(Divide and Conquer)的核心思想:“分而治之”。在编程里,分治算法能把一个复杂的大问题,拆成若干个结构相同的小问题,分别解决后,再把小问题的答案合并起来,得到最终结果。

比如,你想知道全班有多少人。老师可以先把班级分成4个小组,每组数完人数,再把4个数字加起来,就是全班总人数。分治就是这种“先分、再算、最后合”的套路。

分治的三步走

所有分治算法都遵循三个步骤:

  1. 分解(Divide)​​​:把原问题拆成若干个规模较小的、与原问题形式相同的子问题。
  2. 解决(Conquer)​​​:递归地解决每个子问题。如果子问题小到可以直接算出答案(比如只剩一个数),就不再递归。
  3. 合并(Combine)​​​:把子问题的结果组合成原问题的答案。

这三个步骤就像收拾书包:

  • 分解​​:先把书、作业本、文具分别拿出来。
  • 解决​​:把书按大小叠好,作业本按科目放好,文具装进笔袋。
  • 合并​​:最后把整理好的所有东西放回书包。

例子1:用分治法求数组最大值(入门必看)

虽然用循环求最大值更简单,但分治的框架能让你看清“分解—解决—合并”的过程。下面这段代码就是典型的分治写法:

cpp
#include <iostream>
#include <vector>
using namespace std;

// 求数组arr在区间[left, right]内的最大值
int findMax(const vector<int>& arr, int left, int right) {
    if (left == right) {                        // 只剩一个数,直接返回
        return arr[left];
    }
    int mid = left + (right - left) / 2;        // 找到中间位置
    int leftMax = findMax(arr, left, mid);      // 递归求左半部分最大值
    int rightMax = findMax(arr, mid + 1, right);// 递归求右半部分最大值
    return max(leftMax, rightMax);               // 合并:取左右中较大的
}

int main() {
    vector<int> arr = {3, 7, 2, 9, 5};          // 待求数组
    int maxVal = findMax(arr, 0, arr.size() - 1);
    cout << "最大值 = " << maxVal << endl;       // 输出 9
    return 0;
}

代码解释​​:

  • left 和 right 是当前要检查的数组区间下标。
  • 当 left == right 时,区间里只有一个数,这个数就是最大值(递归的“终止条件”)。
  • 否则,把区间从中间切开,分别处理左边和右边。mid = left + (right - left) / 2 可以避免 (left+right) 可能出现的溢出问题,是推荐的写法。
  • 左右两边的最大值都算出来后,用 max() 选出更大的那个作为整个区间的最大值。

递归过程​​(以数组 {3,7,2,9,5} 为例):

findMax(0,4)
   ├─ findMax(0,2)
   │    ├─ findMax(0,1)
   │    │    ├─ findMax(0,0) → 3
   │    │    └─ findMax(1,1) → 7
   │    │    → max(3,7) = 7
   │    └─ findMax(2,2) → 2
   │    → max(7,2) = 7
   └─ findMax(3,4)
        ├─ findMax(3,3) → 9
        └─ findMax(4,4) → 5
        → max(9,5) = 9
   → max(7,9) = 9

最终得到最大值9。

例子2:归并排序——分治的明星应用

归并排序是分治算法最经典的案例。它的思想很简单:要把一个无序数组排好序,先把它切成两半,分别排序,再把两个有序的子数组合并成一个整体有序的数组。

生活中的类比​​:老师手里有两堆按身高排好的队伍(左队和右队),现在要把它们合并成一支整体按身高排好的队伍。做法是:每次从两队的最前面各拉一个人出来,比较身高,矮的先进入新队伍,直到两队都完成。

下面是用C++实现的归并排序完整代码:

cpp
#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序区间 [left, mid] 和 [mid+1, right]
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);   // 临时数组,用于存放合并结果
    int i = left, j = mid + 1, k = 0;     // i指向左半部分开头,j指向右半部分开头

    // 把两个区间中较小的元素依次放入temp
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    // 处理左半部分剩余的元素
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    // 处理右半部分剩余的元素
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    // 把临时数组中的结果拷回原数组
    for (int p = 0; p < k; ++p) {
        arr[left + p] = temp[p];
    }
}

// 归并排序:对数组arr的区间[left, right]进行排序
void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) {                   // 区间为空或只有一个元素,已经有序
        return;
    }
    int mid = left + (right - left) / 2;  // 分解:找到中间位置
    mergeSort(arr, left, mid);             // 解决:递归排序左半部分
    mergeSort(arr, mid + 1, right);        // 解决:递归排序右半部分
    merge(arr, left, mid, right);          // 合并:把两个有序子数组合并
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    cout << "排序结果:";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

合并过程详解​​(以两个有序子数组 {27,38,43} 和 {3,9,82} 为例):

  • 比较 27 和 3:3小 → 放入temp
  • 比较 27 和 9:9小 → 放入temp
  • 比较 27 和 82:27小 → 放入temp
  • 比较 38 和 82:38小 → 放入temp
  • 比较 43 和 82:43小 → 放入temp
  • 右半部分只剩 82,直接放入temp 得到 {3,9,27,38,43,82}。

例子3:最大子段和——分治也能做

你在操场上有一排同学的零花钱数额(有正有负),要选出一段连续的同学,使他们的零花钱之和最大,这就是最大子段和​问题。分治可以这样处理:

  1. 分解​​:把数组从中点切成左右两半。
  2. 解决​​:递归求出左半部分的最大子段和、右半部分的最大子段和。
  3. 合并​​:最大子段可能还有一种情况——跨越了中点。这时需要从中点向左右两侧扩展,分别找到中点左边能取到的最大后缀和、中点右边能取到的最大前缀和,相加就是跨越中点的最大子段和。最后取三者最大值。

虽然这个问题也有更快的动态规划解法,但分治思路同样清晰,且能延伸到“平面最近点对”等更复杂的题目。

新手常犯的四个错误

  1. 忘记写递归终止条件 如果没有 if (left == right) return ...,递归会一直分下去,直到数组越界或栈溢出。哪怕只有一层也要检查。
  2. 切分点mid计算溢出 老式写法 (left + right) / 2 当 left 和 right 都很大时可能整数溢出。用 left + (right - left) / 2 更安全。
  3. 合并时索引搞混乱 比如归并排序中,temp 数组的下标和原数组的对应关系容易写错。建议用临时数组从0开始存,拷回时用 arr[left + p] = temp[p]。
  4. 假设子问题一定能合并 有些分治问题(比如快速排序)不需要显式合并,但必须保证子问题的解能组合成原问题的解。如果合并方法不对,结果就是错的。

完整可运行示例(归并排序)

上面已经给出了归并排序的完整代码。你可以直接复制到编译器里运行,看看数组 {38,27,43,3,9,82,10} 排序后的结果。如果想测试更多数据,可以把 arr 替换成自己喜欢的数字。

相关指引

学完分治的基本框架,你还可以去了解:

  • 快速排序​​:也是分治思想,但它不需要额外数组,原地排序,更高效。
  • 二分查找​​:最简单的分治——每次把查找范围砍掉一半。
  • 棋盘覆盖​​:用L型骨牌覆盖棋盘的经典分治问题。
  • 平面最近点对​​:像我们开头提到的,分治配合排序能高效找出平面上距离最近的两个点。
  • CDQ分治​​:一种高级分治技巧,常用于处理三维偏序等问题。

分治算法的魅力在于:它把复杂问题层层简化,直到变成一眼能看出的答案。多练几道题,你就能体会到“大事化小,小事化了”的编程智慧。试着用分治去解决“求数组逆序对”或“最大子段和”吧,它们会是你提高算法能力的绝佳伙伴!

同类知识点