在做题中学习（77）：快排

解法：快排

思路：

1.快排排一趟，递归分出来的左区间和右区间（一趟的思想，看我的前一个文章：颜色分类题解）

2.递归：想清楚 函数头 和 返回条件怎么写

        函数头：把递归想成一个黑盒，默认它一定能完成任务，函数头就是nums,l,r 意思是在nums数组中的[l,r]区间排好序。

        返回条件：l >=r  ，l == r证明递归到只剩 1个元素，l > r证明递归到空，都不用进一步排序。

3.优化：等概率的取区间内任意元素为key，复杂度渐进式最低，详情看算法导论

4.解惑：为什么一定要颜色分类的思想解决快排的一趟？ 

        因为如果只把数组分为两部分，比如下图：

随机的基准值元素如何取？

顺便分析：时间复杂度

完整代码：

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) //参数的意思，完成[l,r]这个区间数据的快速排序{if(l >= r) return;int key = GetRandnum(nums,l,r);int left = l-1,right = r+1;//一趟快排for(int i = l;i<nums.size();) //注意i的初始化{if(nums[i] < key)swap(nums[++left],nums[i++]);else if(nums[i] == key)i++;else if(nums[i] > key){if(right == i) break;swap(nums[--right],nums[i]);}}//分完一次，递归[l,left] key [right,r]qsort(nums,l,left);qsort(nums,right,r);}int GetRandnum(vector<int>& nums,int l,int r){int randnum = rand();return nums[(randnum % (r - l + 1)) + l];}
};