归并排序
觉得不错的话记得点个赞呀~
归并排序采用了分治的策略，对数组进行排序。如图：
图片引自：https://www.cnblogs.com/chengxiao/p/6194356.html
不断二分，在无法二分时进行比较，并排序，用递归的方法实现比较好理解。 在存储的时候，我们用两个数组分别存储左侧和右侧的值。由于对数组进行排序过程中，并不会改变原有数组中的值，我们可以直接用原有数组来存储结果。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int INF = 1e9 + 7;
int L[N], R[N];
int ans[N];
// 合并
void Merge(int l, int mid, int r) {
int n1 = mid - l + 1;
int n2 = r - mid;
// 从原有数组中把左侧的值和右侧的值分别存储在l数组和r数组中
for (int i = 0; i < n1; i++) L[i] = ans[l + i];
for (int i = 0; i < n2; i++) R[i] = ans[mid + 1 + i];
// 这里把边界外的第一个值设置为INF，就代替了当l或r中某个数组为空时的代码
L[n1] = R[n2] = INF;
int i = 0, j = 0;
for(int k = l; k <= r; k++) {
if (L[i] <= R[j]) {
ans[k] = L[i++];
} else {
ans[k] = R[j++];
}
}
}
// 不断二分
// l : 左边界
// r : 右边界
void MSort(int l, int r) {
int center = (l + r) / 2;
// 当l < r时，说明lr之间只存在一个元素，不需要进行合并
if (l < r) {
MSort(l, center);
MSort(center + 1, r);
Merge(l, center, r);
}
}
void MergeSort(int size) {
int l = 0, r = size - 1;
MSort(l, r); // 调用函数
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> ans[i];
}
MergeSort(n);
for (int i = 0; i < n; i++) {
cout << ans[i] << "\t";
}
return 0;
}
/*
10
8 5 9 2 6 3 7 1 10 4
*/
