分治算法
基本概念
把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
step1分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3合并：将各个子问题的解合并为原问题的解。
归并排序
归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治)策略(分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
代码如下：
#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int is1[N], is2[N]; // `is1` 为主数组，`is2` 为辅助数组
// 合并两个有序子数组的函数
void merge(int low, int mid, int high) {
int i = low, j = mid + 1, k = low; // 初始化 i, j, k 指针
// 合并两个有序子数组
while (i <= mid && j <= high) {
if (is1[i] < is1[j]) {
is2[k++] = is1[i++]; // 左子数组元素更小，拷贝到辅助数组
}
else {
is2[k++] = is1[j++]; // 右子数组元素更小，拷贝到辅助数组
}
}
// 处理左子数组剩余元素
while (i <= mid) {
is2[k++] = is1[i++];
}
// 处理右子数组剩余元素
while (j <= high) {
is2[k++] = is1[j++];
}
// 将辅助数组中的合并结果拷贝回主数组
for (int i = low; i <= high; i++) {
is1[i] = is2[i];
}
}
// 归并排序递归函数
void mergesort(int l, int r) {
if (l >= r) {
return; // 如果子数组长度为1或无效，直接返回
}
int mid = (l + r) >> 1; // 计算中间索引
mergesort(l, mid); // 递归排序左半部分
mergesort(mid + 1, r); // 递归排序右半部分
merge(l, mid, r); // 合并两个有序子数组
}
int main() {
int n;
cin >> n; // 输入数组长度
// 输入数组元素
for (int i = 1; i <= n; i++) {
cin >> is1[i];
}
// 归并排序
mergesort(1, n);
// 输出排序后的数组
for (int i = 1; i <= n; i++) {
cout << is1[i] << ' ';
}
cout << endl;
return 0;
}
代码模板
// 合并排序函数
void merge_sort(int q[], int l, int r)
{
// 如果子数组只有一个元素或为空，则无需排序
if (l >= r) return;
// 计算中间点
int mid = l + r >> 1;
// 递归地排序左半部分
merge_sort(q, l, mid);
// 递归地排序右半部分
merge_sort(q, mid + 1, r);
// 定义临时数组用于合并
int k = 0, i = l, j = mid + 1;
int tmp[r - l + 1]; // 临时数组大小为当前处理的子数组大小
// 合并两个已排序的子数组
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; // 将较小的元素放入临时数组
else tmp[k ++ ] = q[j ++ ]; // 将较小的元素放入临时数组
// 将左半部分剩余的元素添加到临时数组
while (i <= mid) tmp[k ++ ] = q[i ++ ];
// 将右半部分剩余的元素添加到临时数组
while (j <= r) tmp[k ++ ] = q[j ++ ];
// 将临时数组中的元素复制回原数组
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}