编辑代码

/* 元素交换 */
function swap(arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
/**
 * 找中值
 * 保证  arr[min] <= arr[mid] <= arr[max]。
 * 合理的找出中值，确定pivot是选中间值 or 第一个位置 or 最后一个位置 ，可减少后续的对比次数
 */
function findPivot(arr, start, end) {
    const len = end - start
    let mid = start + (len >> 1) //0 -> 7 4
    let min = start
    let max = end - 1

    if (arr[min] > arr[mid]) {
        let temp = min
        min = mid;
        mid = temp
    }
    if (arr[mid] > arr[max]) {
        let temp = mid
        mid = max
        max = temp
    }

    if (arr[min] > arr[mid]) {
        let temp = min
        min = mid
        mid = temp
    }
    return mid
}


function partition(arr, left, right) {
    // 以 nums[left] 作为基准数
    let i = left,
        j = right;

    let mid = findPivot(
        arr,
        left,
        right
    );
    // 将中位数交换至数组最左端
    swap(arr, left, mid);
    // 以 nums[left] 作为基准数
    while (i < j) {
        while (i < j && arr[j] >= arr[left]) {
            j -= 1; // 从右向左找首个小于基准数的元素
        }
        while (i < j && arr[i] <= arr[left]) {
            i += 1; // 从左向右找首个大于基准数的元素
        }

        swap(arr, i, j); // 交换这两个元素
    }
    swap(arr, i, left); // 将基准数交换至两子数组的分界线,也就是最终空的那个位置
    return i; // 返回基准数的索引
}


const findKthLargest = (arr, k) => {
    const len = arr.length
    // left,right 为索引
    function quickSort(left, right) {
        // 子数组长度为 1 时终止递归
        if (left > right) return;

        // 得到基准值
        const pivotIndex = partition(arr, left, right);

        if (len - k < pivotIndex) {
            quickSort(left, pivotIndex - 1);
        } else {
            quickSort(pivotIndex + 1, right);
        }
    }
    quickSort(0, len - 1)
    return arr[len - k]
}


const arr = [9, 8, 7, 6, 5, 4, 2, 1]
const arr2 = [9, 8, 5, 4, 2, 1, 7, 6]
const arr3 = [2, 1, 9, 8, 5, 4, 7, 6]
console.log(findKthLargest(arr, 1))
console.log(findKthLargest(arr2, 2))
console.log(findKthLargest(arr3, 3))
console.log(findKthLargest(arr2, 4))
console.log(findKthLargest(arr3, 5))