AcWing 787. 归并排序
原题链接
简单
作者:
沉心方可沉淀
,
2021-02-06 20:05:18
,
所有人可见
,
阅读 447
又是两种方法
C++代码
#include<bits/stdc++.h>using namespace std;
const int N=1e5+10;
int a[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i)
{
cin>>a[i];
}
sort(a+1,a+1+n);
//直接调用sort函数,先是快乐方法
for(int i=1;i<=n;i)
{
cout<<a[i]<<” “;
}
return 0;
}
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
//差点被数字空间卡死,注意最好像我这样定义一下,方便多了,之前没提
int a[N];
int n,b[N];
void init()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
}
void msort(int a[],int l,int r)
{
if(l==r)
return;
int s=(l+r)/2;
msort(a,l,s);
//递归
msort(a,s+1,r);
int i=l,j=s+1;
int m=l;
while(i<=s&&j<=r)
{
if(a[i]<=a[j])
{
b[m]=a[i];
m++;
i++;
}
else
{
b[m]=a[j];
m++;
j++;
}
}
while(i<=s)
{
b[m]=a[i];
m++;
i++;
}
while(j<=r)
{
b[m]=a[j];
m++;
j++;
}
for(int i=l;i<=r;i++)
a[i]=b[i];
}
void result()
{
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
}
int main()
{
init();
msort(a,1,n);
result();
return 0;
}