分治算法
分治算法通过将问题分解为更小的子问题来解决，是算法设计的重要思想。在竞赛编程中，分治算法常用于解决排序、搜索、数值计算等问题，具有优美的递归结构和高效的时间复杂度。
归并排序 - 分治算法的经典应用
归并排序完美体现了分治思想：将数组分为两半，递归排序每一半，然后合并已排序的部分。
归并排序实现
#include <iostream>
#include <vector>
using namespace std;
class MergeSort {
public:
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);
}
private:
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 i = 0; i < k; i++) {
arr[left + i] = temp[i];
}
}
};
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
cout << "原数组: ";
for (int x : arr) cout << x << " ";
cout << endl;
MergeSort ms;
ms.mergeSort(arr, 0, arr.size() - 1);
cout << "排序后: ";
for (int x : arr) cout << x << " ";
cout << endl;
return 0;
}归并排序的时间复杂度为O(n log n)，空间复杂度O(n)。它是稳定排序算法，在链表排序中特别有用。
快速排序与快速选择
快速排序通过选择基准元素将数组分为两部分，每部分独立排序。快速选择算法可以高效找到第k小的元素。
快速排序与快速选择
#include <iostream>
#include <vector>
#include <random>
using namespace std;
class QuickSort {
public:
void quickSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
// 随机化选择基准，避免最坏情况
int randomIndex = left + rand() % (right - left + 1);
swap(arr[left], arr[randomIndex]);
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
// 快速选择 - 找第k小元素
int quickSelect(vector<int>& arr, int left, int right, int k) {
if (left == right) return arr[left];
int randomIndex = left + rand() % (right - left + 1);
swap(arr[left], arr[randomIndex]);
int pivotIndex = partition(arr, left, right);
if (pivotIndex == k) return arr[pivotIndex];
else if (pivotIndex > k) return quickSelect(arr, left, pivotIndex - 1, k);
else return quickSelect(arr, pivotIndex + 1, right, k);
}
private:
int partition(vector<int>& arr, int left, int right) {
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
if (i < j) arr[i++] = arr[j];
while (i < j && arr[i] <= pivot) i++;
if (i < j) arr[j--] = arr[i];
}
arr[i] = pivot;
return i;
}
};
int main() {
srand(time(nullptr));
vector<int> arr = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
cout << "原数组: ";
for (int x : arr) cout << x << " ";
cout << endl;
QuickSort qs;
vector<int> sortArr = arr;
qs.quickSort(sortArr, 0, sortArr.size() - 1);
cout << "排序后: ";
for (int x : sortArr) cout << x << " ";
cout << endl;
// 测试快速选择
int k = 5; // 第6小的元素（0-indexed）
int kthSmallest = qs.quickSelect(arr, 0, arr.size() - 1, k);
cout << "第" << (k + 1) << "小的元素: " << kthSmallest << endl;
return 0;
}快速排序平均时间复杂度O(n log n)，最坏情况O(n²)。快速选择算法可以在O(n)平均时间内找到第K小元素。
最大子数组问题
最大子数组问题可以用分治算法优雅地解决，时间复杂度为O(n log n)。
最大子数组 - 分治解法
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class MaxSubarray {
public:
struct Result {
int maxSum;
int left;
int right;
Result(int sum = INT_MIN, int l = -1, int r = -1)
: maxSum(sum), left(l), right(r) {}
};
Result maxSubarrayDC(vector<int>& arr, int left, int right) {
// 基础情况：单个元素
if (left == right) {
return Result(arr[left], left, right);
}
int mid = left + (right - left) / 2;
// 递归找左右两半的最大子数组
Result leftResult = maxSubarrayDC(arr, left, mid);
Result rightResult = maxSubarrayDC(arr, mid + 1, right);
// 找跨越中点的最大子数组
Result crossResult = maxCrossingSubarray(arr, left, mid, right);
// 返回三种情况中的最大值
if (leftResult.maxSum >= rightResult.maxSum &&
leftResult.maxSum >= crossResult.maxSum) {
return leftResult;
} else if (rightResult.maxSum >= leftResult.maxSum &&
rightResult.maxSum >= crossResult.maxSum) {
return rightResult;
} else {
return crossResult;
}
}
private:
Result maxCrossingSubarray(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;
}
}
// 从中点+1向右扩展的最大和
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 Result(leftSum + rightSum, maxLeft, maxRight);
}
};
// Kadane算法对比（O(n)）
int kadane(vector<int>& arr) {
int maxSoFar = arr[0];
int maxEndingHere = arr[0];
for (int i = 1; i < arr.size(); i++) {
maxEndingHere = max(arr[i], maxEndingHere + arr[i]);
maxSoFar = max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
int main() {
vector<int> arr = {-2, -3, 4, -1, -2, 1, 5, -3};
cout << "数组: ";
for (int x : arr) cout << x << " ";
cout << endl;
MaxSubarray ms;
MaxSubarray::Result result = ms.maxSubarrayDC(arr, 0, arr.size() - 1);
cout << "分治算法 - 最大和: " << result.maxSum << endl;
cout << "子数组索引: [" << result.left << ", " << result.right << "]" << endl;
cout << "子数组: ";
for (int i = result.left; i <= result.right; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "Kadane算法: " << kadane(arr) << endl;
return 0;
}分治方法考虑三种情况：最大子数组在左半部分、右半部分或跨越中点。时间复杂度为O(n log n)。
最近点对问题
使用分治算法在二维平面中找最近点对，时间复杂度O(n log n)，优于暴力方法的O(n²)。
最近点对问题
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <float.h>
using namespace std;
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
double distanceTo(const Point& other) const {
return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
}
};
class ClosestPair {
public:
double findClosestPair(vector<Point>& points) {
// 按x坐标排序
sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
return a.x < b.x;
});
return closestPairRec(points, 0, points.size() - 1);
}
private:
double closestPairRec(vector<Point>& points, int left, int right) {
int n = right - left + 1;
// 基础情况：小数组用暴力方法
if (n <= 3) {
return bruteForce(points, left, right);
}
int mid = left + (right - left) / 2;
Point midPoint = points[mid];
// 递归找左右两半的最近点对
double leftMin = closestPairRec(points, left, mid);
double rightMin = closestPairRec(points, mid + 1, right);
double minDist = min(leftMin, rightMin);
// 找接近分割线的点
vector<Point> strip;
for (int i = left; i <= right; i++) {
if (abs(points[i].x - midPoint.x) < minDist) {
strip.push_back(points[i]);
}
}
// 按y坐标排序条带
sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) {
return a.y < b.y;
});
// 在条带中找最近点对
return min(minDist, stripClosest(strip, minDist));
}
double bruteForce(vector<Point>& points, int left, int right) {
double minDist = DBL_MAX;
for (int i = left; i <= right; i++) {
for (int j = i + 1; j <= right; j++) {
minDist = min(minDist, points[i].distanceTo(points[j]));
}
}
return minDist;
}
double stripClosest(vector<Point>& strip, double minDist) {
double min_val = minDist;
for (int i = 0; i < strip.size(); i++) {
// 最多检查7个点（几何证明）
for (int j = i + 1; j < strip.size() &&
(strip[j].y - strip[i].y) < min_val; j++) {
min_val = min(min_val, strip[i].distanceTo(strip[j]));
}
}
return min_val;
}
};
int main() {
vector<Point> points = {
Point(2, 3), Point(12, 30), Point(40, 50), Point(5, 1),
Point(12, 10), Point(3, 4), Point(1, 1), Point(8, 7)
};
cout << "点集:" << endl;
for (int i = 0; i < points.size(); i++) {
cout << "(" << points[i].x << ", " << points[i].y << ")" << endl;
}
ClosestPair cp;
double closestDistance = cp.findClosestPair(points);
cout << "最近点对距离: " << closestDistance << endl;
return 0;
}算法按x坐标分割点集，在每一半中找最近点对，然后检查分割线附近的点。关键洞察是在条带中最多只需检查7个点。
关键要点
- 分治算法将问题分解为更小的子问题，递归求解，然后合并结果
- 时间复杂度通常遵循递推关系T(n) = aT(n/b) + f(n)，使用主定理分析
- 常见应用：排序算法、最近点对、最大子数组、快速乘法
- 通常提供具有优雅递归结构的最优解