利用快速排序算法将读入的N个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料,掌握后独立完成。
输入格式
第11行为一个正整数N,第22行包含 N个空格隔开的正整数ai ,为你需要进行排序的数,数据保证了Ai不超过10的9次方。
输出格式
将给定的N个数从小到大输出,数之间空格隔开,行末换行且无空格。
输入输出样例
输入
5
4 2 4 5 1
输出
1 2 4 4 5
源代码:
#include<stdio.h>
int n,a[1000001],t;
void qsort(int l,int r)
{
if(l>=r)
return;
int mid=a[(l+r)/2];
int i=l,j=r;
while(i<=j)
{
while(a[i]<mid&&i<=j) i++;
while(a[j]>mid&&i<=j) j--;
if(i<=j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
i++;
j--;
}
}
if(l<j)
qsort(l,j);
if(i<r)
qsort(i,r);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
qsort(1, n);
for (int i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
}