215.数组中的第K个最大元素（Medium）
读完本文，可以去力扣解决如下题目：
215.数组中的第 k 个最大元素（medium）
快速选择算法是一个非常经典的算法，和快速排序算法是亲兄弟。
原始题目很简单，给你输入一个无序的数组nums和一个正整数k，让你计算nums中第k大的元素。
那你肯定说，给nums数组排个序，然后取第k个元素，也就是nums[k-1]，不就行了吗？
当然可以，但是排序时间复杂度是o(nlogn)，其中n表示数组nums的长度。
我们就想要第k大的元素，却给整个数组排序，有点杀鸡用牛刀的感觉，所以这里就有一些小技巧了，可以把时间复杂度降低到o(nlogk)甚至是o(n)，下面我们就来具体讲讲。
力扣第 215 题「数组中的第 k 个最大元素」就是一道类似的题目，函数签名如下：
intfindkthlargest(int[]nums,intk);
只不过题目要求找第k个最大的元素，和我们刚才说的第k大的元素在语义上不太一样，题目的意思相当于是把nums数组降序排列，然后返回第k个元素。
比如输入nums = [2,1,5,4], k = 2，算法应该返回 4，因为 4 是nums中第 2 个最大的元素。
这种问题有两种解法，一种是二叉堆（优先队列）的解法，另一种就是标题说到的快速选择算法（quick select），我们分别来看。
二叉堆解法
二叉堆的解法比较简单，实际写算法题的时候，推荐大家写这种解法，先直接看代码吧：
二叉堆（优先队列）是比较常见的数据结构，可以认为它会自动排序，我们前文 手把手实现二叉堆数据结构 实现过这种结构，我就默认大家熟悉它的特性了。
看代码应该不难理解，可以把小顶堆pq理解成一个筛子，较大的元素会沉淀下去，较小的元素会浮上来；当堆大小超过k的时候，我们就删掉堆顶的元素，因为这些元素比较小，而我们想要的是前k个最大元素嘛。当nums中的所有元素都过了一遍之后，筛子里面留下的就是最大的k个元素，而堆顶元素是堆中最小的元素，也就是「第k个最大的元素」。
二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过k，所以插入和删除元素的复杂度是o(logk)，再套一层 for 循环，总的时间复杂度就是o(nlogk)。空间复杂度很显然就是二叉堆的大小，为o(k)。
这个解法算是比较简单的吧，代码少也不容易出错，所以说如果笔试面试中出现类似的问题，建议用这种解法。唯一注意的是，java 的priorityqueue默认实现是小顶堆，有的语言的优先队列可能默认是大顶堆，可能需要做一些调整。
快速选择算法
快速选择算法比较巧妙，时间复杂度更低，是快速排序的简化版，一定要熟悉思路。
我们先从快速排序讲起。
快速排序的逻辑是，若要对nums[lo..hi]进行排序，我们先找一个分界点p，通过交换元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，然后递归地去nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点，最后整个数组就被排序了。
快速排序的代码如下：
关键就在于这个分界点索引p的确定，我们画个图看下partition函数有什么功效：
索引p左侧的元素都比nums[p]小，右侧的元素都比nums[p]大，意味着这个元素已经放到了正确的位置上，回顾快速排序的逻辑，递归调用会把nums[p]之外的元素也都放到正确的位置上，从而实现整个数组排序，这就是快速排序的核心逻辑。
那么这个partition函数如何实现的呢？看下代码：
熟悉快速排序逻辑的读者应该可以理解这段代码的含义了，这个partition函数细节较多，上述代码参考《算法4》，是众多写法中最漂亮简洁的一种，所以建议背住，这里就不展开解释了。
好了，对于快速排序的探讨到此结束，我们回到一开始的问题，寻找第k大的元素，和快速排序有什么关系？
注意这段代码：
intp=partition(nums,lo,hi);
我们刚说了，partition函数会将nums[p]排到正确的位置，使得nums[lo..p-1] < nums[p] < nums[p+1..hi]。
那么我们可以把p和k进行比较，如果p k说明第k大的元素在nums[lo..p-1]中。
所以我们可以复用partition函数来实现这道题目，不过在这之前还是要做一下索引转化：
题目要求的是「第k个最大元素」，这个元素其实就是nums升序排序后「索引」为len(nums) - k的这个元素。
这样就可以写出解法代码：
这个代码框架其实非常像我们前文二分搜索框架的代码，这也是这个算法高效的原因，但是时间复杂度为什么是o(n)呢？按理说类似二分搜索的逻辑，时间复杂度应该一定会出现对数才对呀？
其实这个o(n)的时间复杂度是个均摊复杂度，因为我们的partition函数中需要利用双指针技巧遍历nums[lo..hi]，那么总共遍历了多少元素呢？
最好情况下，每次p都恰好是正中间(lo + hi) / 2，那么遍历的元素总数就是：
n + n/2 + n/4 + n/8 + … + 1
这就是等比数列求和公式嘛，求个极限就等于2n，所以遍历元素个数为2n，时间复杂度为o(n)。
但我们其实不能保证每次p都是正中间的索引的，最坏情况下p一直都是lo + 1或者一直都是hi - 1，遍历的元素总数就是：
n + (n - 1) + (n - 2) + … + 1
这就是个等差数列求和，时间复杂度会退化到o(n^2)，为了尽可能防止极端情况发生，我们需要在算法开始的时候对nums数组来一次随机打乱：
前文洗牌算法详解写过随机乱置算法，这里就不展开了。当你加上这段代码之后，平均时间复杂度就是o(n)了，提交代码后运行速度大幅提升。
总结一下，快速选择算法就是快速排序的简化版，复用了partition函数，快速定位第 k 大的元素。相当于对数组部分排序而不需要完全排序，从而提高算法效率，将平均时间复杂度降到o(n)。
原文标题：快排亲兄弟：快速选择算法详解
文章出处：【微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
高频变压器发热原因及散热解决办法
大疆宣布暂停俄罗斯乌克兰业务，就此事正与相关人员协商
变配电智能化系统：提高效率与安全性
涂料供应商PPG开发新型锂电池电极
串励电机怎么测量好坏 串励电机怎么测量好坏
215.数组中的第K个最大元素（Medium）
工频电机可以变频使用吗_工频电机调速范围
苹果ios10.3.2手留余香！等ios11上市ios10.3.2才放弃32位系统设备的封杀！这下果粉可以放心了
谷歌计划研发内置摄像头的可穿戴自拍戒指
千名学生走进AI课堂 主角阿尔法蛋备受关注
智能硬件新玩法 瞄准养宠神器猫猫狗狗宠物饮水机
PCB设计中的常见不良现象分析
北汽自主品牌在北京地区将全面停止燃油车的生产
安路科技：基于FPGA SoC的呼吸机系统设计
分享一个不错的安全系统报警电路图
两款多点控制电子开关电路图
这不是神话:用手势就能驱动的显示器亮相
安泰高压放大器设计的意义及其应用价值
运放电压跟随电路的特点和性能
采用多线程与虚拟化等独特技术的测试芯片
215.数组中的第 k 个最大元素（medium）
快速选择算法是一个非常经典的算法，和快速排序算法是亲兄弟。
原始题目很简单，给你输入一个无序的数组nums和一个正整数k，让你计算nums中第k大的元素。
那你肯定说，给nums数组排个序，然后取第k个元素，也就是nums[k-1]，不就行了吗？
当然可以，但是排序时间复杂度是o(nlogn)，其中n表示数组nums的长度。
我们就想要第k大的元素，却给整个数组排序，有点杀鸡用牛刀的感觉，所以这里就有一些小技巧了，可以把时间复杂度降低到o(nlogk)甚至是o(n)，下面我们就来具体讲讲。
力扣第 215 题「数组中的第 k 个最大元素」就是一道类似的题目，函数签名如下：
intfindkthlargest(int[]nums,intk);
只不过题目要求找第k个最大的元素，和我们刚才说的第k大的元素在语义上不太一样，题目的意思相当于是把nums数组降序排列，然后返回第k个元素。
比如输入nums = [2,1,5,4], k = 2，算法应该返回 4，因为 4 是nums中第 2 个最大的元素。
这种问题有两种解法，一种是二叉堆（优先队列）的解法，另一种就是标题说到的快速选择算法（quick select），我们分别来看。
二叉堆解法
二叉堆的解法比较简单，实际写算法题的时候，推荐大家写这种解法，先直接看代码吧：
二叉堆（优先队列）是比较常见的数据结构，可以认为它会自动排序，我们前文 手把手实现二叉堆数据结构 实现过这种结构，我就默认大家熟悉它的特性了。
看代码应该不难理解，可以把小顶堆pq理解成一个筛子，较大的元素会沉淀下去，较小的元素会浮上来；当堆大小超过k的时候，我们就删掉堆顶的元素，因为这些元素比较小，而我们想要的是前k个最大元素嘛。当nums中的所有元素都过了一遍之后，筛子里面留下的就是最大的k个元素，而堆顶元素是堆中最小的元素，也就是「第k个最大的元素」。
二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过k，所以插入和删除元素的复杂度是o(logk)，再套一层 for 循环，总的时间复杂度就是o(nlogk)。空间复杂度很显然就是二叉堆的大小，为o(k)。
这个解法算是比较简单的吧，代码少也不容易出错，所以说如果笔试面试中出现类似的问题，建议用这种解法。唯一注意的是，java 的priorityqueue默认实现是小顶堆，有的语言的优先队列可能默认是大顶堆，可能需要做一些调整。
快速选择算法
快速选择算法比较巧妙，时间复杂度更低，是快速排序的简化版，一定要熟悉思路。
我们先从快速排序讲起。
快速排序的逻辑是，若要对nums[lo..hi]进行排序，我们先找一个分界点p，通过交换元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，然后递归地去nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点，最后整个数组就被排序了。
快速排序的代码如下：
关键就在于这个分界点索引p的确定，我们画个图看下partition函数有什么功效：
索引p左侧的元素都比nums[p]小，右侧的元素都比nums[p]大，意味着这个元素已经放到了正确的位置上，回顾快速排序的逻辑，递归调用会把nums[p]之外的元素也都放到正确的位置上，从而实现整个数组排序，这就是快速排序的核心逻辑。
那么这个partition函数如何实现的呢？看下代码：
熟悉快速排序逻辑的读者应该可以理解这段代码的含义了，这个partition函数细节较多，上述代码参考《算法4》，是众多写法中最漂亮简洁的一种，所以建议背住，这里就不展开解释了。
好了，对于快速排序的探讨到此结束，我们回到一开始的问题，寻找第k大的元素，和快速排序有什么关系？
注意这段代码：
intp=partition(nums,lo,hi);
我们刚说了，partition函数会将nums[p]排到正确的位置，使得nums[lo..p-1] < nums[p] < nums[p+1..hi]。
那么我们可以把p和k进行比较，如果p k说明第k大的元素在nums[lo..p-1]中。
所以我们可以复用partition函数来实现这道题目，不过在这之前还是要做一下索引转化：
题目要求的是「第k个最大元素」，这个元素其实就是nums升序排序后「索引」为len(nums) - k的这个元素。
这样就可以写出解法代码：
这个代码框架其实非常像我们前文二分搜索框架的代码，这也是这个算法高效的原因，但是时间复杂度为什么是o(n)呢？按理说类似二分搜索的逻辑，时间复杂度应该一定会出现对数才对呀？
其实这个o(n)的时间复杂度是个均摊复杂度，因为我们的partition函数中需要利用双指针技巧遍历nums[lo..hi]，那么总共遍历了多少元素呢？
最好情况下，每次p都恰好是正中间(lo + hi) / 2，那么遍历的元素总数就是：
n + n/2 + n/4 + n/8 + … + 1
这就是等比数列求和公式嘛，求个极限就等于2n，所以遍历元素个数为2n，时间复杂度为o(n)。
但我们其实不能保证每次p都是正中间的索引的，最坏情况下p一直都是lo + 1或者一直都是hi - 1，遍历的元素总数就是：
n + (n - 1) + (n - 2) + … + 1
这就是个等差数列求和，时间复杂度会退化到o(n^2)，为了尽可能防止极端情况发生，我们需要在算法开始的时候对nums数组来一次随机打乱：
前文洗牌算法详解写过随机乱置算法，这里就不展开了。当你加上这段代码之后，平均时间复杂度就是o(n)了，提交代码后运行速度大幅提升。
总结一下，快速选择算法就是快速排序的简化版，复用了partition函数，快速定位第 k 大的元素。相当于对数组部分排序而不需要完全排序，从而提高算法效率，将平均时间复杂度降到o(n)。
原文标题：快排亲兄弟：快速选择算法详解
文章出处：【微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
高频变压器发热原因及散热解决办法
大疆宣布暂停俄罗斯乌克兰业务，就此事正与相关人员协商
变配电智能化系统：提高效率与安全性
涂料供应商PPG开发新型锂电池电极
串励电机怎么测量好坏 串励电机怎么测量好坏
215.数组中的第K个最大元素（Medium）
工频电机可以变频使用吗_工频电机调速范围
苹果ios10.3.2手留余香！等ios11上市ios10.3.2才放弃32位系统设备的封杀！这下果粉可以放心了
谷歌计划研发内置摄像头的可穿戴自拍戒指
千名学生走进AI课堂 主角阿尔法蛋备受关注
智能硬件新玩法 瞄准养宠神器猫猫狗狗宠物饮水机
PCB设计中的常见不良现象分析
北汽自主品牌在北京地区将全面停止燃油车的生产
安路科技：基于FPGA SoC的呼吸机系统设计
分享一个不错的安全系统报警电路图
两款多点控制电子开关电路图
这不是神话:用手势就能驱动的显示器亮相
安泰高压放大器设计的意义及其应用价值
运放电压跟随电路的特点和性能
采用多线程与虚拟化等独特技术的测试芯片