基于快排的疾速抉择算法
问题
最近做到一个经典的leetcode题目，因为分类在“分治算法”标签中，故思考用分治的思维解决，题目如下，
剑指offer40.最小的k个数
输出整数数组 arr ，找出其中最小的 k 个数。例如，输出4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输出：arr = [3,2,1], k = 2 输入：[1,2] 或者 [2,1]
示例 2：
输出：arr = [0,1,2,1], k = 1 输入：[0]
本题有三种解法，别离是简略粗犷的排序而后取前k个数，基于堆排序的一种改良算法，以及本文所讲的疾速抉择算法。第一种办法实际上是将数组中的所有元素先排序，而后取前k个，然而咱们想真的有必要将所有元素一次性的进行排序吗？咱们只须要晓得最小的k个元素即可，所以咱们是否能够对局部元素进行排序，而后判断再对局部元素进行排序，一旦达到咱们的指标（曾经筛选出k个元素了），全身而退。实践上这是要比一次性排序所需的工夫少得多的。第二种和第三种办法都带有这类思维。
- 回顾疾速排序
在快排中也是使用了分治的思维，每一次排序中，咱们会在数组中抉择一个元素作为枢轴（能够了解为杠杆点，个别抉择数组第一个点，当然也能够随机抉择），通过双指针low,high将比这个枢轴元素小的元素放在它的左侧，比它大的元素放在它的右侧。这样就实现了一次初步的排序，以这个枢轴为中心点能够划分成左右两块，右边的元素都比枢轴小，左边的元素都比枢轴大。进而对左右两个子数组再次进行以上的步骤，这也体现了分而治之的思维。具体过程看下图，
疾速排序外围代码如下，
while(lo < hi){ while(lo<hi && arr[hi] >= pivotkey)hi--; arr[lo] = arr[hi]; while(lo<hi && arr[lo] <= pivotkey)lo++; arr[hi]=arr[lo]; } arr[lo]=pivotkey;- 疾速抉择的原理
疾速抉择就是在上述根底上进行革新的，咱们能够看到，上图中曾经通过一个杠杆点将数组分成了左右两块，称为左块和右块，左块的元素必定比杠杆点小或等于，那么因为题目中是要求咱们选取最小的k个点，咱们假如k等于4，那么上图中曾经达到了咱们的指标，间接返回杠杆点的下标即可。也就是low+1-start == k即返回low，其中start为low刚进来的值，因为low的初值不肯定都是0，用lo+1-start示意左块的元素个数。
上面思考若low-start+1 < k，这阐明左块的元素数量还不够，然而左块中的元素和杠杆点必定曾经是最小k个元素中的了，所以咱们只须要递归一次，对lo+1，nums.size()-1区间上的元素再找出 k-(low+1-start),就能够返回这个区间上的杠杆点的坐标即为最终的后果。
若low-start+1 > k,这阐明左块的元素太多了，那么咱们就能够齐全舍弃右块，在区间start,lo-1上找到k个最小元素即可。
这有点像一种变相的分治，即分完之后并不对每一个块进行治理，而是有抉择的进行治理。
- 疾速抉择的代码实现
int Partition(vector<int>& arr,int lo,int hi,int k){ if(hi - lo + 1 == k )return hi; //留神：若传进来区间的长度曾经等于k了，那么没必要快排了，间接返回即可。 int start = lo; //不然很难选中一个刚刚好的杠杆点，从而会造成重复横跳的状况。 int pivotkey = arr[lo]; while(lo < hi){ //快排外围代码 while(lo<hi && arr[hi] >= pivotkey)hi--; arr[lo] = arr[hi]; while(lo<hi && arr[lo] <= pivotkey)lo++; arr[hi]=arr[lo]; } arr[lo]=pivotkey; if(lo-start+1 == k)return lo; //返回杠杆点的下标 else if(lo-start+1 < k){ return Partition(arr,lo+1,arr.size()-1,k-(lo-start+1)); } else{ return Partition(arr,start,lo-1,k); } }