题解 | #排序#手写快速排序法

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