分治思想 排序数组

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size() - 1);
        return nums;
    }

    void qsort(vector<int>& nums,int l,int r)
    {
        //递归结束条件
        if(l>=r) return;
        //随机选取key
        int key = GetRandM(nums,l,r);
        int i = l,left = l - 1,right = r + 1;
        //确保过程中被划分为预先设好的4个有规律的区域
        while(i<right)
        {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] == key) i++;
            else swap(nums[--right],nums[i]);
        }
        //[l,left][left+1,right-1][right,r]
        //递归左右区间
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    //得到区间内一个随机元素
    int GetRandM(vector<int>& nums,int left,int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
};