AcWing 787. AC_any 模板 归并排序
原题链接
简单
作者:
AC_any
,
2021-04-08 16:41:30
,
所有人可见
,
阅读 194
细节
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
#define loop(x) for(int i=0;i<x;i++)
#define read(x) scanf("%d",&x)
int n;
int a[100004];
int tmp[100004];
void merge(int l,int r){
if(l>=r) return ;
//选取中点
int mid=l+r>>1;
merge(l,mid);
merge(mid+1,r);
//左右两半都已经排好
int i=l,j=mid+1,k=0;
while(i<=mid && j<=r){
if(a[i]<=a[j]) tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
//复写回来
loop(k) a[l+i]=tmp[i];//小心起点,且不要多加加
}
int main(){
cin>>n;
loop(n) read(a[i]);
merge(0,n-1);
loop(n) printf("%d ",a[i]);
}