排序

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 64MB，其他语言 128MB

描述

给定你一个长度为 \(n\) 的整数数列。
请你使用任意排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
数据范围 \(1≤n≤100000\)
禁止使用 sort 函数

输入描述

输入共两行，第一行包含整数 \(n\)。
第二行包含 \(n\) 个整数（所有整数均在 \(0∼10^9\) 范围内），表示整个数列。

输出描述

输出格式输出共一行，包含 \(n\) 个整数，表示排好序的数列。

用例输入 1

5
3 1 2 4 5

用例输出 1

1 2 3 4 5

解析

推荐查看 https://acwing.com/solution/content/16777

代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e5+5;
int n,a[N],tmp[N];

void quick_sort(int l,int r)
{
	if(l>=r) return;
	int i=l-1,j=r+1, pivot=a[(l+r)>>1];
	while(i<j)
	{
		do i++; while(a[i]<pivot);
		do j--; while(a[j]>pivot);
		if(i<j) swap(a[i],a[j]);
	}
	quick_sort(l,j), quick_sort(j+1,r);
	return;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	quick_sort(1,n);
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}