题解 | #快排1#

pivot是基准元素，按照基准元素将数组分为两部分（大于和小于），pos就是分割后正确的基准元素位置，在寻找pos位置的过程中进行交换。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    int partition(vector<int>& arr,int left,int right){
        int pivot=arr[left];
        int pos=left;
        for(int i=left+1;i<=right;i++){
            if(arr[i]<pivot){
                pos++;
                if(pos!=i){
                    swap(arr[pos],arr[i]);
                }
            }
        }
        arr[left]=arr[pos];
        arr[pos]=pivot;
        return pos;
    }
    
    void quick_sort(vector<int>& arr,int left,int right){
        if(left>=right){
            return;
        }
        int mid=partition(arr,left,right);
        quick_sort(arr,left,mid-1);
        quick_sort(arr,mid+1,right);
    }
    
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quick_sort(arr,0,arr.size()-1);
        return arr;
    }
};