快速

 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 }