从分治的思想下优化快速排序算法
快速排序是对于数组元素进行排序的一种方法，基本原理是：在数组中随任意选择一个元素作为参考（key），使得数组分为两部分，左部分小于等于key右部分大于key，这样经过一次排序后key的值就会在他最终正确的位置，接下来就是让左右两个子数组继续重复上述操作，知道把数组分成1或2个元素（递归）。但这种方法如果遇到数组中有重复元素会增加时间复杂度，如果数组都是同一个元素，那么每次进行排序后，key都会到最右端，这样时间复杂度就是n平方了。因此，我们需要优化一下，用三指针把数组分成三部分再进行递归。
关于随机key的选取我们也非常重要，在算法导论中写到随机地选取key值也有利于优化时间复杂度，一会我们在代码中演示。
剩下的就是每次把数组分割后进行排序，然后每个子数组再次被分割再次排序。排序方法参考分治算法排序
vector sortarray(vetor&nums){ srand(time(NULL)); qsort(nums,0,nums.size()-1); return nums;}void qsort(vector%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&nums,int left,int right){ int r=rand(); return nums[r%(right-left+1)+left]; //控制随机的下标是在每一个子数组内}
