快速排序

快速排序时间复杂度O(nlogn)

对一个序列A进行排序，使得A[1]左侧院所都小于A[1],右侧元素都大于A[1]，速度最快的做法是双指针法。

#include<iostream>
using namespace std;
int Partition(int A[],int left, int right){
    int tmp=A[left];
    while(left<right){
        while(left<right&&A[right]>tmp){
            right--;
        }
        A[left]=A[right];
        while(left<right&&A[left]<=tmp){
            left++;
        }
        A[right]=A[left];
    }
    A[left]=tmp;
    return left;
}

void quickSort(int A[],int left,int right){
    if(left<right){
        int pos=Partition(A,left,right);
        quickSort(A,left,pos-1);
        quickSort(A,pos+1,right);
    }
}

int main(){
    int n;
    cin>>n;
    int* num=new int[n];
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    quickSort(num,0,n-1);
    for(int i=0;i<n;i++){
        cout<<num[i]<<endl;
    }
}