class Solution {
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;
    }

    int partition(vector<int>&arr,int l,int r)
    {
        int x = arr[l];
        while( l < r)
        {
            while(l<r&&arr[r]>=x){r--;}
            arr[l]=arr[r];
            while(l<r&&arr[l]<=x){l++;}
            arr[r]=arr[l];
        }
        arr[l] = x;
        return l;
    }

    void quicksort(vector<int>&arr,int l,int r)
    {
        if(l<r)
        {
            int mid = partition(arr, l, r);
            quicksort(arr, l, mid);
            quicksort(arr,mid+1,r);
        }
        return;
    }
};

快速排序