归并排序

# include<iostream>
using namespace std;

const int M=1e5+5;
int n,a[M],b[M];

void merge(int l,int r){
	if(l==r) return;
	int mid=(l+r)/2,i=l,j=mid+1,cnt=l;
	merge(l,mid);
	merge(j,r);
	while(i<=mid&&j<=r){
		if(a[i]<a[j]) b[cnt++]=a[i++];
		else b[cnt++]=a[j++];
	}
	while(i<=mid) b[cnt++]=a[i++];
	while(j<=r) b[cnt++]=a[j++];
	for(int i=l;i<=r;++i) a[i]=b[i];
}

int main(){
	cin>>n;
	for(int i=0;i<n;++i) cin>>a[i];
	merge(0,n-1);
	for(int i=0;i<n;++i) cout<<a[i]<<" ";
	return 0;
}

快速排序

# include<iostream>
using namespace std;

int n,a[10005];

void qsort(int l,int r){
	if(l>=r) return;
	int i=l,j=r,mid=a[(l+r)/2];
	while(i<=j){
		while(a[i]<mid) i++;
		while(a[j]>mid) j--;
		if(i<=j){
			swap(a[i],a[j]);
			i++,j--;
		}
	}
	qsort(l,j);
	qsort(i,r);
} 

int main(){
	cin>>n;
	for(int i=0;i<n;++i) cin>>a[i];
	qsort(0,n-1);
	for(int i=0;i<n;++i) cout<<a[i]<<" ";
	return 0;
}