C++分治算法详解（从零开始掌握递归分治法）

经典案例：归并排序（Merge Sort）

归并排序是分治法教程中最常被引用的例子。它的时间复杂度稳定为 O(n log n)，非常适合用来理解分治思想。

算法思路

• 将数组从中间分成左右两半（分解）
• 对左右两半分别进行归并排序（递归解决）
• 将两个已排序的子数组合并成一个有序数组（合并）

C++ 实现代码

#include <iostream>#include <vector>using namespace std;// 合并两个已排序的子数组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;    // 比较并合并    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 idx = 0; idx < k; ++idx)        arr[left + idx] = temp[idx];}// 归并排序主函数void mergeSort(vector<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);   // 合并两部分    }}// 测试函数int main() {    vector<int> nums = {38, 27, 43, 3, 9, 82, 10};    cout << "原始数组: ";    for (int x : nums) cout << x << " ";    cout << endl;    mergeSort(nums, 0, nums.size() - 1);    cout << "排序后数组: ";    for (int x : nums) cout << x << " ";    cout << endl;    return 0;}

为什么选择 C++ 实现分治算法？

C++ 提供了高效的内存管理和强大的标准模板库（STL），使得实现递归分治C++程序既简洁又高效。同时，C++ 的指针和引用机制让我们能灵活控制数据传递方式，避免不必要的拷贝开销。

分治算法的适用场景

除了归并排序，以下问题也常用分治法解决：

• 快速排序（Quick Sort）
• 二分查找（Binary Search）
• 最近点对问题（Closest Pair of Points）
• 大整数乘法（Karatsuba 算法）
• 矩阵乘法（Strassen 算法）

小结

通过本教程，你已经掌握了C++分治算法的基本思想和实现方法。记住：分治的关键在于“如何分”和“如何合”。多练习像归并排序这样的经典例子，你将逐步建立起对算法设计入门的信心。继续加油，未来的算法高手就是你！