笔记-找出数组中第K大的值（快速排序、堆排序实现）

题目： 找出数组中第K大的值，要求对数组不能进行排序，时间复杂度为O(nlog2k)

快速排序实现

思路： 若对快速排序的底层逻辑尚不熟悉，建议先阅读 快速排序的原理（从小到大排序） 以夯实基础。本题的核心约束在于禁止对数组进行全量排序，因此我们需要对标准的快速排序算法进行针对性改造，将其调整为从大到小的分区策略。寻找第K大的元素，本质上等同于定位数组中索引为 k-1 的位置（假设索引从0开始）。在分区过程中，pivot 的最终落点 par 起到了关键的分界作用。若 par 大于 k-1，说明目标值位于当前分区的左半部分，因为左侧包含了比 pivot 更大的元素，且数量足以覆盖前 k 个最大值，故应在左侧递归查找；反之，若 par 小于 k-1，则意味着左侧仅包含 par 个比 pivot 大的数，不足以构成前 k 大，目标值必然位于右侧，需在右侧继续搜索；当 par 恰好等于 k-1 时，表明左侧正好存在 k 个相对于整个数组而言较大的元素，此时 pivot 即为所求。

注意:左侧的数并不是从大到小排好序的，只是当par=k-1时，左侧的数都>=array[k-1] ，右边的都<=array[k-1] 所以array[par]正好为第k大的数

代码实现：

    public class