分治思想 排序数组

题目

这是一道经典的关于分治思想的算法题，适合刚接触分治的小白。

. - 力扣（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代码：

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;//随机选取keyint 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];}
};