题目描述
利用快速排序算法将读入的NN个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）
输入输出格式
输入格式：
第1行为一个正整数NN，第2行包含N个空格隔开的正整数ai，为你需要进行排序的数，数据保证了Ai不超过1000000000。
输出格式：
将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
输入样例#1：
5
4 2 4 5 1
输出样例#1：
1 2 4 4 5
说明
对于20\%20%的数据，有N≤1000N≤1000；
对于100\%100%的数据，有N≤100000N≤100000。
题解
快速排序模版，代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std ;
pair<int,int>partition( vector<int> &a ,int l, int r ){
int less = l-1,more = r ;
while ( l < more ){
if ( a[l] < a[r] ){
swap(a[l++],a[++less]) ;
}
else if ( a[l] > a[r] ){
swap(a[l],a[--more]) ;
}
else{
l ++ ;
}
}
swap(a[more],a[r]) ;
return make_pair(less+1,more);
}
void quickSort(vector<int> &a , int l , int r ){
if ( l < r ){
swap(a[l +rand()%(int)(r-l+1)],a[r]) ;
pair<int,int> p = partition(a,l,r) ;
quickSort(a,l,p.first-1) ;
quickSort(a,p.second+1,r) ;
}
return ;
}
int main(){
vector<int> a ;
int n ;
cin >> n ;
for ( int i = 0 ; i < n ; i ++ ){
int num ;
cin >> num ;
a.push_back(num) ;
}
quickSort(a,0,a.size()-1) ;
for ( int i = 0 ; i < a.size() ; i ++ ){
cout << a[i] << " " ;
}
return 0 ;
}