快排

class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers2(vector<int>& A) {
        // Write your code here
        /*
        vector<int>temp(A.size(),0);
        mergeSort(A,temp,0,A.size()-1);
        */
        quickSort(A,0,A.size()-1);
    }
    
    
    
  void quickSort(vector<int>& A,int left,int right) {
        if(left >= right) { 
            return;
        }
        int index = partion(A,left,right);
        int temp = A[index];
        A[index] = A[left];
        A[left] = temp;
        quickSort(A,left,index-1);
        quickSort(A,index+1,right);
}
    
    int partion(vector<int>& A,int left,int right) {
        int pivot = A[left];
        int i = left;
        int j = right+1;
        while(i < j ) {
            while(A[--j]>pivot) {
                
            }
            while((i<j) && (A[++i]<pivot)) {
              
            }
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        };
//返回i和j都可以，注意分析left+1 ＝ right这种情况
        return j;
    }
}