【算法】数组中，求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;