一、编程题：215. 数组中的第K个最大元素（快速选择）
1.题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 LeetCode题目链接。
2.示例1：
输入: [3,2,1,5,6,4], k = 2
输出: 5
3.示例2：
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
4.提示：
- 1 <= k <= nums.length <= 105
- -104 <= nums[i] <= 104
二、解题思路
1.思路
解决方法1（个人想法）：
本题主要考察的是堆排序跟快速排序，但两种排序本人掌握的不好，所以只能再去看这两排序的原理。下面要讲解的快速选择算法是在快速排序上得来，至于堆排序待后续补充（还没理解透）；
解决方法2（快速选择）：
- Step1.首先设定一个分界值，通过与该分界值将数组分成左右两部分；
- Step2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值，而右边部分中各元素都大于或等于分界值；
- Step3.然后就能得到当前分界值所在位置，注意这里分界值的位置是已经排序好的，不会再移动。所以可以通过判断第K大（length-k）位置落在分界值的那个区间，来决定对哪边进行递归处理即可
- Step4.重复上述过程，可以看出，这是一个递归定义。通过递归处理第k大所处的区间就能得到该值。
快速排序切分原理：
把一个数组切分成两个子数组的基本思想：
- Step1.找一个基准值，用两个指针分别指向数组的头部和尾部；
- Step2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
- Step3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
- Step4.交换当前左边指针位置和右边指针位置的元素；
- Step5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
三、代码实现
每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一（快速选择）：
class Solution { int partition(int[] nums, int left, int right, int k){ //递归结束条件 if(left == right) return nums[k]; int key = nums[left]; //作为划分数组的基值 int arrayleft = left; // 指向当前基值的位置 int arrayright = right+1; //指向右边后一个元素 while(arrayleft < arrayright){ //比x小的数放在左边 //先从右往左扫描，找到一个比基准值小的元素 while(nums[++arrayleft] < key) if(arrayleft == right) break; //比x大的数放在右边 //再从左往右扫描，找一个比基准值大的元素 while(nums[--arrayright] > key) if(arrayleft == left) break;; if(arrayleft < arrayright) swap(nums, arrayleft, arrayright); } //arrayright为基值的位置 swap(nums, left,arrayright); if(k == arrayright) return nums[k]; else if(k < arrayright) return partition(nums, left, arrayright-1, k); else return partition(nums, arrayright+1, right, k); } void swap(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public int findKthLargest(int[] nums, int k) { int num_length = nums.length; return partition(nums, 0, num_length-1, num_length-k); } }
提交结果：
总结
以上就是今天要讲的内容，快速排序算是比较常见的算法了，但过段时间不用的话就会忘的特别快，感觉是没理解透，至于堆排序是我想不到了，只能说平时用到这些排序算法都比较少，以至于适用于什么场景都不清楚，快速选择是看了三叶姐想法之后自己理了一边快速排序写了出来的，其印象比较深刻，所以就赶紧记录一下这个方法，开阔一下思路。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
