题目描述
给定你一个长度为n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在1~109范围内),表示整个数列。
输出格式
输出共一行,包含 n 个整数,表示排好序的数列。
数据范围
1≤n≤100000
输入样例
5
3 1 2 4 5
输出样例
1 2 3 4 5
算法1(归并排序)
C++ 代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int temp[N];
void gb(int l,int r){
if(l>=r){
return;
}
int mid=(l+r)/2;
gb(l,mid);
gb(mid+1,r);
int k=0;
int i=l;
int j=mid+1;
while(i<=mid && j<=r){
if(a[i]<a[j]){
temp[k++]=a[i++];
}
else{
temp[k++]=a[j++];
}
}
while(i<=mid){
temp[k++]=a[i++];
}
while(j<=r){
temp[k++]=a[j++];
}
k=0;
for(int i=l;i<=r;i++){
a[i]=temp[k++];
}
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
gb(1,n);
for(int i=1;i<=n;i++){
if(i!=1){
cout << " ";
}
cout << a[i];
}
return 0;
}
算法2(STL sort)
C++ 代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int main()
{
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
if(i!=1){
cout << " ";
}
cout << a[i];
}
cout << endl;
return 0;
}