归并排序
**分治算法
归并排序,它有两大核心操作.
一个是将数组一分为二,一个无序的数组成为两个数组.
另外一个操作就是,合二为一,将两个有序数组合并成为一个有序数组.**
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N]; //tmp为临时数组
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;
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++]; //将每段存好的数先存在tmp数组中
//把临时数组中的元素复制到目标数组里,因为我们后面进行递归操作,要继续对q进行操作
for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
//注意此处i=l,因为我们排序的数组的区间是[l , r ]
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}