基于快排的疾速抉择算法

1. 问题

   最近做到一个经典的 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 个元素了），全身而退。实践上这是要比一次性排序所需的工夫少得多的。第二种和第三种办法都带有这类思维。

2. 回顾疾速排序

   在快排中也是使用了分治的思维，每一次排序中，咱们会在数组中抉择一个元素作为枢轴（能够了解为杠杆点，个别抉择数组第一个点，当然也能够随机抉择），通过双指针 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;

1. 疾速抉择的原理

   疾速抉择就是在上述根底上进行革新的，咱们能够看到，上图中曾经通过一个杠杆点将数组分成了左右两块，称为左块和右块，左块的元素必定比杠杆点小或等于，那么因为题目中是要求咱们选取最小的 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 个最小元素即可。

   这有点像一种变相的分治，即分完之后并不对每一个块进行治理，而是有抉择的进行治理。

2. 疾速抉择的代码实现

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);
        }
    }