归并排序
归并排序可以想象成两堆书,按页数排序
而且这两堆书本就是从小到大或从大到小排好序的(由函数先递归后排序可知)
以从小到大为例子
左边剩余第一本书页数小于右边剩余第一本书的页数
那么将左边第一本书放入res书堆中(当然是最后面)
反之则将右边第一本书放入res书堆中
最后还剩哪堆直接按顺序放入res书堆即可
#include<iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N];
int res[N];
void merge_sort(int arr[], int l, int r){
if(l >= r) return;
int mid = (l + r) >> 1;
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r)
if(arr[i] <= arr[j]) res[k++] = arr[i++];
else res[k++] = arr[j++];
while(i <= mid) res[k++] = arr[i++];
while(j <= r) res[k++] = arr[j++];
for(int m = l, n = 0; m <= r; m++,n++) arr[m] = res[n];
}
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;
}