快速排序  也叫做分区排序  时间复杂度O(n*logn)  不稳定

分区排序，使得左侧子序列中的元素都小于基准元素，右侧子序列中的元素都大于等于基准元素

 

 1 #include<iostream>
 2 using namespace std;
 3 int Paritition(int (&a)[5],int low,int high){
 4     int pivotpos=low;
 5     int pivot=a[low];//基准元素 
 6     for(int i=low+1;i<=high;i++){//一个一个比较 
 7         if(a[i]<pivot){
 8             pivotpos++;
 9             if(pivotpos!=i){
10                 int temp=a[i];
11                 a[i]=a[pivotpos];
12                 a[pivotpos]=temp;
13             }
14         }
15     }
16     a[low]=a[pivotpos];
17     a[pivotpos]=pivot;
18     return pivotpos;
19 }
20 void Quicksort(int (&a)[5],int left,int right){
21     if(left<right){
22         int pivotpos=Paritition(a,left,right);//排序并获得基准元素该在的位置下标
23         Quicksort(a,left,pivotpos-1);
24         Quicksort(a,pivotpos+1,right);
25     }
26 }
27 int main(){
28     int a[5]={9,8,7,6,5};
29     Quicksort(a,0,4);
30     for(int i=0;i<5;i++) cout<<a[i]<<endl; 
31     return 0;
32 }