快排亲兄弟：快速选择算法详解

作者：labuladong  公众号：labuladong读完本文，可以去力扣解决如下题目：215.数组中的第 K 个最大元素（Medium）快速选择算法是一个非常经典的算法，和快速排序算法是亲兄弟。原始题目很简单，给你输入一个无序的数组nums和一个正整数k，让你计算nums中第k大的元素。那你肯定说，给nums数组排个序，然后取第k个元素，也就是nums[k-1]，不就行了吗？当然可以，但是排序时间复杂度是O(NlogN)，其中N表示数组nums的长度。我们就想要第k大的元素，却给整个数组排序，有点杀鸡用牛刀的感觉，所以这里就有一些小技巧了，可以把时间复杂度降低到O(NlogK)甚至是O(N)，下面我们就来具体讲讲。力扣第 215 题「数组中的第 K 个最大元素」就是一道类似的题目，函数签名如下：int findKthL ………………………………