题解 | #排序#

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