从分治的思想下优化快速排序算法

快速排序是对于数组元素进行排序的一种方法，基本原理是：在数组中随任意选择一个元素作为参考（key），使得数组分为两部分，左部分小于等于key右部分大于key，这样经过一次排序后key的值就会在他最终正确的位置，接下来就是让左右两个子数组继续重复上述操作，知道把数组分成1或2个元素（递归）。但这种方法如果遇到数组中有重复元素会增加时间复杂度，如果数组都是同一个元素，那么每次进行排序后，key都会到最右端，这样时间复杂度就是n平方了。因此，我们需要优化一下，用三指针把数组分成三部分再进行递归。

关于随机key的选取我们也非常重要，在算法导论中写到随机地选取key值也有利于优化时间复杂度，一会我们在代码中演示。

剩下的就是每次把数组分割后进行排序，然后每个子数组再次被分割再次排序。排序方法参考分治算法排序

vector<int> sortarray(vetor<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;int i=l,left=l-1,right=r+1;int key=getrandom(nums,l,r);while(i<right){if(nums[i]<key) swap(nums[++left],nums[i++];else if(nums[i]==key) i++;else swap(nums[--right],nums[i]);}//[left+1,right-1]已经在正确的位置上qsort(nums,l,left);qsort(nums,right,r);
}int getrandom(vector<int>&nums,int left,int right)
{int r=rand();return nums[r%(right-left+1)+left];//控制随机的下标是在每一个子数组内}