题目
这是一道经典的关于分治思想的算法题，适合刚接触分治的小白。
. - 力扣（LeetCode）
思路
采用递归分治的思想，也就是快速排序的模拟，这里先确定每趟递归的作用：
在一个规定的区间内，随机选择一个key，将key放在正确的位置，也就是左边的元素都比它小，右边的元素都比它大，实现方法如下：
通过三个指针（i，left，right）将数组划分为4个区域。
我们确保处理过程中：
left左边全是<key的元素
left 1到i-1全是==key的元素
i到right-1都是待扫描的元素
right右边都是>key的元素
当i和right相遇时循环结束
最后数组就被划分为3个区域：
left左边全是<key的元素，left 1到right-1全是==key的元素，right右边都是>key的元素。
最后再递归处理左边<key的区间和右边>key的区间，进行上述相同的操作。
AC代码：
代码语言：javascript复制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];
}
};
