题目描述
利用快速排序算法将读入的N个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）
输入输出格式
输入格式： 输入文件sort.in的第1行为一个正整数N，第2行包含N个空格隔开的正整数a[i]，为你需要进行排序的数，数据保证了A[i]不超过1000000000。
输出格式： 输出文件sort.out将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
输入样例#1： 5 4 2 4 5 1 输出样例#1： 1 2 4 4 5
说明
对于20%的数据，有N≤1000；
对于100%的数据，有N≤100000。
代码
#include<iostream>
#include<cstring>
using namespace std;
void quicksort(
int a[],
int ac,
int ak)
{
if(ac>=ak)
return ;
swap(a[ac],a[(ac+ak)/
2]);
int head=ac,tail=ak,x=a[ac];
while(head<tail)
{
while(head<tail&&a[tail]>x)tail--;
if(head<tail)a[head++]=a[tail];
while(head<tail&&a[head]<x)head++;
if(head<tail)a[tail--]=a[head];
}
a[head]=x;
quicksort(a,ac,head-
1);
quicksort(a,head+
1,ak);
}
int main()
{
int n,a[
100005];
memset(a,
0,
sizeof(a));
cin>>n;
for(
int i=
0;i<n;i++)
cin>>a[i];
quicksort(a,
0,n-
1);
for(
int i=
0;i<n-
1;i++)
cout<<a[i]<<
' ';
cout<<a[n-
1];
return 0;
}
