题目来源：https://leetcode.cn/problems/kth-largest-element-in-an-array/

大致题意：
找出未排序数组中第 k 大的元素

思路

如果要找出数组中第 k 大的元素，最简单的方法就是直接排序，然后按照索引取出第 k 大的元素即可

不过题目并未要求将数组排序，直接排序会有冗余操作

较优的方法由根据堆排序的思想，每轮选出当前堆最大元素，时间复杂度为 O(log n)，经过 k 次后选出的最大元素即为第 k 大元素，这样时间复杂度为 O(k * log n)

上述方法也有缺陷，因为其相当于将最大的 k 个元素全部排序了

快排的分界方法，方法每执行一次就会确定一个元素在排序后数组中的位置

于是可以使用快排的分解方法来求第 k 大的元素，每次分界方法执行后确定的位置与 k 的关系有：

1. 当前位置等于 k，那么当前位置对应元素即为第 k 大元素
2. 当前位置小于 k，那么第 k 大元素应该在当前位置右侧，接下只用在右侧元素中找即可
3. 当前位置大于 k，那么第 k 大元素应该在当前位置左侧，接下只用在左侧元素中找即可

具体实现时，可以通过两个标志位 start 和 end 表示待寻找元素所在范围，初始时为 0 和 n - 1，接下来根据分界方法的分界位置与 k 的关系更新两个标志位

代码：

public class FindKthLargest {public int findKthLargest(int[] nums, int k) {int n = nums.length;// 获取分界位置int ith = getPivot(nums, 0, n - 1);// 升序排序，需要将 k 转化为第 k 小的元素k = n - k;// 查找范围int start = 0;int end = n - 1;// 根据分界位置与 k 的关系更新两个标志位while (ith != k) {// 分界位置小于 k，往右侧找if (ith < k) {start = ith + 1;ith = getPivot(nums, start, end);} else {// 分界位置大于 k，往左侧找end = ith - 1;ith = getPivot(nums, start, end);}}return nums[ith];}// 获取当前数组首元素在 [left, right] 中的排序位置public int getPivot(int[] nums, int left, int right) {int l = left;int r = right;int pivot = nums[left];while (l < r) {while (l < r && nums[r] >= pivot) {r--;}nums[l] = nums[r];while (l < r && nums[l] <= pivot) {l++;}nums[r] = nums[l];}nums[l] = pivot;return l;}
}