SOURCE

/**
 * TopN问题
 * 找到数组中前N个大的数
 */

function Partition(arr, l, r) {
	let low = l;
	let high = r;
    const pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high --;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) low ++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

function TopN(arr, n) {
	const index = _TopN(arr, 0, arr.length - 1, n);
	const newArr = [];
	for (let i = index; i < arr.length; i++) {
		newArr.push(arr[i]);
	}
	return newArr;
}

/**
 * 分治找到一个基准数
 * 使得比该基准数大的数个数恰好为n
 */
function _TopN(arr, low, high, n) {
	const pivot = Partition(arr, low, high);
	const topnum = arr.length - pivot;
    console.log(low, high, pivot, JSON.stringify(arr));
	if (topnum === n) return pivot;
	else if (topnum > n) return _TopN(arr, pivot + 1, high, n);
	else return _TopN(arr, low, pivot - 1, n);
}

const arr = [7, 5, 4, 11, 6, 8, 10, 20];
console.log(TopN(arr, 3));