AcWing 787. 归并排序
原题链接
简单
作者:
Charles__
,
2020-03-03 23:14:15
,
所有人可见
,
阅读 759
写代码时内存超限,简直离谱
C++ 代码
#include<iostream>
using namespace std;
int tmp[100010],a[100010],n;
//左闭右开
//尼玛内存超限可能是递归爆了?
void merge_sort(int l,int r)
{
//注意看这里啊!!!!!!!!!!
//写成l>=r就爆内存了
if(l>=r-1) return ;
int mid = (l+r)>>1;
merge_sort(l,mid);
merge_sort(mid,r);
//合并,默认上面已经排序好左边和右边
int i = l , j = mid ,p = 0 ;
while(i<mid&&j<r)
if(a[i]<a[j])
tmp[p++]=a[i++];
else
tmp[p++]=a[j++];
while(i<mid)
tmp[p++]=a[i++];
while(j<r)
tmp[p++]=a[j++];
for(int i=l,k=0;i<r;i++)
a[i]=tmp[k++];
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
merge_sort(0,n);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
}