当前位置：首页 > ai >正文

C++经典的数据结构与算法之经典算法思想：分治法（Divide and Conquer）

ai 2025/9/7 19:00:21

分治法（Divide and Conquer）：将复杂问题化繁为简的算法思想

分治法是一种重要的算法设计范式，其核心思想是将一个复杂问题分解为若干个规模较小的子问题，递归解决子问题后，再将子问题的解合并为原问题的解。这种"分而治之"的策略广泛应用于各种算法中，如排序（归并排序、快速排序）、查找（二分查找）、矩阵乘法（Strassen算法）等。

一、分治法的基本步骤

分治法通常遵循以下三个步骤：

分解（Divide）：将原问题分解为若干个与原问题结构相似但规模更小的子问题。
解决（Conquer）：递归求解子问题。若子问题规模足够小，则直接求解（ base case）。
合并（Combine）：将子问题的解合并为原问题的解。

分治法的三步流程：分解→解决→合并

二、经典应用：归并排序（Merge Sort）

归并排序是分治法的典型实现，完整体现了"分解-解决-合并"的过程。

#include <vector>
#include <iostream>
using namespace std;// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组存储两个子数组vector<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++];}k++;}// 处理剩余元素while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}// 分治法核心：分解问题并递归求解
void mergeSort(vector<int>& arr, int left, int right) {if (left < right) {  // 基本情况：子数组长度为1时直接返回// 1. 分解：将数组分为两半int mid = left + (right - left) / 2;  // 避免溢出// 2. 解决：递归排序两个子数组mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 3. 合并：将两个有序子数组合并merge(arr, left, mid, right);}
}// 测试
int main() {vector<int> arr = {12, 11, 13, 5, 6, 7};mergeSort(arr, 0, arr.size() - 1);cout << "排序结果：";for (int num : arr) cout << num << " ";  // 输出：5 6 7 11 12 13return 0;
}

分治分析：

分解：将数组分为两个规模为n/2的子数组（O(1)）。
解决：递归排序两个子数组（2×T(n/2)）。
合并：合并两个有序数组（O(n)）。

时间复杂度：通过主定理可得 T(n) = O(n log n)。

三、经典应用：快速排序（Quick Sort）

快速排序同样基于分治法，但合并步骤被简化（无需显式合并，分区后自然有序）。

#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;// 分区操作：选择基准，将数组分为小于基准和大于基准两部分
int partition(vector<int>& arr, int left, int right) {// 随机选择基准（避免最坏情况）srand(time(0));int pivotIdx = left + rand() % (right - left + 1);swap(arr[pivotIdx], arr[right]);int pivot = arr[right];int i = left - 1;  // 小于基准区域的边界for (int j = left; j < right; j++) {if (arr[j] <= pivot) {swap(arr[++i], arr[j]);}}swap(arr[i + 1], arr[right]);  // 基准放到最终位置return i + 1;  // 返回基准索引
}// 分治法核心
void quickSort(vector<int>& arr, int left, int right) {if (left < right) {  // 基本情况：子数组长度为1时直接返回// 1. 分解：通过分区将数组分为两部分int pivotPos = partition(arr, left, right);// 2. 解决：递归排序两个子数组（无需合并步骤）quickSort(arr, left, pivotPos - 1);quickSort(arr, pivotPos + 1, right);}
}// 测试
int main() {vector<int> arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.size() - 1);cout << "排序结果：";for (int num : arr) cout << num << " ";  // 输出：1 5 7 8 9 10return 0;
}

分治分析：

分解：通过分区将数组分为两个子数组（O(n)）。
解决：递归排序两个子数组（T(k) + T(n-k-1)，k为左子数组规模）。
合并：无需显式合并，分区后子数组已部分有序（O(1)）。

时间复杂度：平均情况 O(n log n)，最坏情况 O(n²)（可通过随机基准优化）。

四、分治法求解最大子数组问题

最大子数组问题是指在一个整数数组中，找到和最大的连续子数组（如股票最佳买卖时机问题）。

#include <vector>
#include <climits>
#include <iostream>
using namespace std;// 查找跨越中点的最大子数组
pair<int, pair<int, int>> findMaxCrossingSubarray(vector<int>& arr, int left, int mid, int right) {// 向左扩展寻找最大和int leftSum = INT_MIN;int sum = 0;int maxLeft = mid;for (int i = mid; i >= left; i--) {sum += arr[i];if (sum > leftSum) {leftSum = sum;maxLeft = i;}}// 向右扩展寻找最大和int rightSum = INT_MIN;sum = 0;int maxRight = mid + 1;for (int i = mid + 1; i <= right; i++) {sum += arr[i];if (sum > rightSum) {rightSum = sum;maxRight = i;}}// 返回跨越中点的最大子数组信息return {leftSum + rightSum, {maxLeft, maxRight}};
}// 分治法求解最大子数组
pair<int, pair<int, int>> findMaxSubarray(vector<int>& arr, int left, int right) {// 基本情况：子数组只有一个元素if (left == right) {return {arr[left], {left, right}};}// 1. 分解：分为左右两个子数组int mid = left + (right - left) / 2;// 2. 解决：递归寻找左右子数组的最大子数组auto leftResult = findMaxSubarray(arr, left, mid);auto rightResult = findMaxSubarray(arr, mid + 1, right);// 3. 合并：比较三种情况（左、右、跨越中点）auto crossResult = findMaxCrossingSubarray(arr, left, mid, right);if (leftResult.first >= rightResult.first && leftResult.first >= crossResult.first) {return leftResult;} else if (rightResult.first >= leftResult.first && rightResult.first >= crossResult.first) {return rightResult;} else {return crossResult;}
}// 测试
int main() {vector<int> arr = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};auto result = findMaxSubarray(arr, 0, arr.size() - 1);cout << "最大子数组和：" << result.first << endl;  // 输出：43cout << "起始索引：" << result.second.first << ", 结束索引：" << result.second.second << endl;  // 7-10return 0;
}