分治算法归并排序

分治算法

基本概念

把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法的基本步骤

分治法在每一层递归上都有三个步骤：

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];
}