问题引入有一个包含大量数据的数组想要快速找到其中第k大的值需要注意的是查找元素是数组排序后的第k个最大的元素而不是第k个不同的元素输入输出如下所示最直接的想法是排序后取第k个时间复杂度为O(nlogn)或者用堆求解TopK问题时间复杂度为O(nlogk)在数据量较大的情况下二者都显得不够高效那么有没有更高效的方法呢这里就引入了快速选择算法它是在快排基础上的进一步优化在求解TopK问题上极为高效时间复杂度仅为O(n)。算法思想快速选择的核心思想与快排类似1、每次选择一个基准元素pivot2、将数组划分为两部分大于等于pivot的放在左边小于pivot的放在右边3、根据pivot的位置与k的关系决定是在左半部分还是右半部分继续查找快速选择算法与快排的核心区别在于快排会递归处理两侧而快速选择算法只处理包含答案的那一侧因此快速选择算法实现将时间复杂度从O(nlogn)降到O(n)。图解算法过程以数组[7,10,4,3,20,15]为例查找第3大元素快速选择算法的过程如下快速选择算法代码实现如下class Solution { int quickselect(vectorint nums,int left,int right,int k) { int tmpnums[right]; int ileft; for(int jleft;jright;j) { if(nums[j]tmp) { swap(nums[i],nums[j]); i; } } swap(nums[i],nums[right]); if(ik) return nums[i]; else if(ik) return quickselect(nums,left,i-1,k); else return quickselect(nums,i1,right,k); } public: int findKthLargest(vectorint nums, int k) { return quickselect(nums,0,nums.size()-1,nums.size()-k); } };int tmpnums[right]选择数组最右端的元素nums[right]作为基准值int lefti用i标记小于基准值的分区位置通过for循环遍历left到right-1的所有元素if(nums[j]tmp)若nums[j]小于基准值tmpswap(nums[i],nums[j])就交换到左侧swap(nums[i],nums[right])最后将基准值放到i位置完成升序分区。分区后if(ik)如果基准位置i恰好等于目标索引k则查找成功nums[i]即为第k大的元素return nums[i]即可。else if(ik)如果i大于目标索引k说明目标在左半部分return quickselect(nums,left,i-1,k)递归处理左侧else如果i小于目标索引k则递归处理右侧return quickselect(num,i1,right,k)。需要注意的是在分区上采取升序策略故主函数findKthLargest传入的目标索引为nums.size()-k对应的是升序排序后第k大元素所在的索引位置即 return quickselect(nums,0,nums.size()-1,nums.size()-k),主函数findKthLargest通过调用quickselect即可找出数组中的第k个最大元素至此快速选择算法执行完成。总结快速选择算法在求解TopK等问题很高效快速选择算法的核心思想是每次选择一个基准值采取升序策略通过一次遍历将数组分为两部分小于基准值的元素放在左边大于基准值的元素放在右边这样基准值最终所在的位置就代表了它在升序排序后的最终索引。完成分区后将基准值的索引i与目标索引k进行比较若ik则找到答案直接返回即可若ik说明第k大的元素在基准值左侧的子数组中则递归处理左半部分若ik说明第k大的元素在基准值右侧的子数组中则递归处理右半部分。每次递归只会处理数组的一半因此快速选择算法的时间复杂度为O(n)。由于其高效的查找效率快速选择算法在数据库查询优化、机器学习和实时系统等领域都有广泛应用在大规模数据处理场景中具有显著的工程实践意义。