AcWing 787. 归并排序
原题链接
简单
作者:
ls131
,
2021-07-30 23:38:24
,
所有人可见
,
阅读 173
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int T;
int n,m;
int tmp[N]; //辅助数组
void merge_sort(int a[],int l,int r)
{
if(l>=r) return; //递归函数先写递归出口
//快排:找中间哨兵 归并:分两段 上下挨个依次比对
int mid=l+r>>1; //位运算
int i=l,j=mid+1;
merge_sort(a,l,mid);merge_sort(a,mid+1,r);
int 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++];
for(int i=l,j=0;i<=r;i++) a[i]=tmp[j++]; //重回原数组
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
merge_sort(a,0,n-1);
for(int i=0;i<n;i++) cout<<a[i]<<' ';
cout<<endl;
return 0;
}