1 #include<bits/stdc++.h>
2 using namespace std;
3 int a[100000010];
4 int part(int* r,int l,int h)//划分函数
5 {
6 int i=l;
7 int j=h;
8 int piv=r[l];//基准元素
9 while(i<j)
10 {
11 while(i<j&&r[j]>piv)//从右向左开始找一个小于等于piv的值
12 {
13 j--;
14 }
15 if(i<j)
16 {
17 swap(r[i++],r[j]);//r[i]和r[j]交换后会 i++ 继续进行操作
18 }
19 while(i<j&&r[i]<=piv)//从左向右开始找一个小于等于piv的值
20 {
21 i++;
22 }
23 if(i<j)
24 {
25 swap(r[i],r[j--]);//r[i]和r[j]交换后会 j-- 继续进行操作
26 }
27 }
28 return i;
29 }
30 void sot(int* r,int l,int h)
31 {
32 int mid;
33 if(l<h){
34 mid=part( r,l,h);
35 sot(r,l,mid-1);
36 sot(r,mid+1,h);
37 }
38
39 }
40 int main()
41 {
42 int n;
43 cin>>n;
44 for(int i=0;i<n;i++)
45 {
46 cin>>a[i];
47 }
48 sot(a,0,n-1);
49 for(int i=0;i<n;i++)
50 {
51 cout<<a[i]<<" ";
52 }
53 cout<<endl;
54 return 0;
55 }