【算法】数组中，求K个最大值

 已知：数组 [8, 9, 15, 20, 3, 5, 7, 2, 6]，求第8个最大值是哪个值？

function quickSort(arr, targetIndex, start) {
    if (arr.length <= 1) return arr[0];
    let left = [];
    let right = [];
    const mid = Math.floor(arr.length / 2);
    const midNum = arr.splice(mid, 1)[0];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > midNum) {
            right.push(arr[i]);
        } else {
            left.push(arr[i]);
        }
    }
    if (left.length + start === targetIndex) {
        return midNum;
    } else if (left.length + start > targetIndex) {
        return quickSort(left, targetIndex, start);
    } else {
        return quickSort(right, targetIndex, left.length + start + 1);
    }
}
const findKthLargest = function (nums, k) {
    const num = quickSort(nums, nums.length - k, 0);
    return num;
};
console.log(findKthLargest([8, 9, 15, 20, 3, 5, 7, 2, 6], 8));

思路：

• 取数组的中间索引元素midNum，循环数组，将小于midNum的元素放到left数组中，大于midNum的元素放到right数组中;
• 比较小于midNum的left 数组的长度 + 之前的递归的左边的数组的长度 与 targetIndex的大小：
• 如果大于targetIndex，继续递归循环left数组；
• 如果小于targetIndex，递归循环right数组；
• 如果等于targetIndex，返回当前中间索引midNum;