有序数组里第 K 大的元素就是index 为 array.length - k 的元素。
快速排序的思路主要就是选一个基准值p，然后将小于p的值放在p的左右，大于p的值放在p的右边，然后对左右数组进行递归。
利用这个思路，当我们找到这个基准值对应的 index，等于我们要找的index时，就可以了，不用管左右两边是否是有序的。

先看未优化版。这里是新建数组分别用来存比基准值小和大的元素

function findKthLargest(input, k) {const len = input.length;if (len < 2) return input;let nums = input.concat([]);const getQuickSortIndex = (startIndex, endIndex) => {const len = endIndex - startIndex + 1;const pivotIndex = (len >>> 1) + startIndex;const pivotValue = nums[pivotIndex];const leftArr = [];const rightArr = [];for (let i = startIndex; i <= endIndex; i++) {if (i === pivotIndex) continue; //不把基准值独立出来，会造成无限递归if (nums[i] <= pivotValue) {leftArr.push(nums[i]);} else {rightArr.push(nums[i]);}}nums.splice(startIndex,len,...[...leftArr, pivotValue, ...rightArr]) ;return startIndex + leftArr.length;};let targetIndex = nums.length - k;let start = 0,end = nums.length - 1;let index = getQuickSortIndex(start, end);while (index != targetIndex) {if (index > targetIndex) {end = index - 1;} else {start = index + 1;}index = getQuickSortIndex(start, end);}return nums[index];
}

然后看优化版，不新建数组，直接在原数组上操作

function getQuickSortIndex(arr, startIndex, endIndex) {let pivot = arr[startIndex];let prev = startIndex;for (let i = startIndex + 1; i <= endIndex; i++) {if (arr[i] < pivot) {prev++;[arr[prev], arr[i]] = [arr[i], arr[prev]];}}arr[startIndex] = arr[prev];arr[prev] = pivot;return prev;
}function findKthLargest_1(nums, k) {const len = nums.length;if (len < 2) return nums;let targetIndex = nums.length - k;let start = 0,end = nums.length - 1;let index = getQuickSortIndex(nums, start, end);while (index != targetIndex) {if (index > targetIndex) {end = index - 1;} else {start = index + 1;}index = getQuickSortIndex(nums, start, end);}return nums[index];
}