快速排序

1.复杂度

时间复杂度：O(nlogn)，最高可达O(n²)
空间复杂度：O(nlogn)

2.代码实现

2.1递归实现

#include<iostream>
using namespace std;
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void quicksort(int aa[],int start,int end){
    if(start>=end)return ;
    int l=start,r=end;
    int p=aa[l];
    while(l<r){
        while(r>l&&aa[r]>=p)r--;
        while(r>l&&aa[l]<=p)l++;
        swap(aa[r],aa[l]);
    }
    swap(aa[l],aa[start]);
    quicksort(aa,start,l-1);
    quicksort(aa,l+1,end);
}
int main(){
    int aa[]={5,4,3,2,1};
    quicksort(aa,0,4);
    for(int a:aa)cout<<a<<" ";
}