Topk快排實作

簡介

通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行

• 1.首先設定一個分界值，通過該分界值将數組分成左右兩部分。
• 2.将大于或等于分界值的資料集中到數組右邊，小于分界值的資料集中到數組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。
• 3.然後，左邊和右邊的資料可以獨立排序。對于左側的數組資料，又可以取一個分界值，将該部分資料分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組資料也可以做類似處理。
• 4.重複上述過程，可以看出，這是一個遞歸定義。通過遞歸将左側部分排好序後，再遞歸排好右側部分的順序。當左、右兩個部分各資料排序完成後，整個數組的排序也就完成了。

let quickTopK = function (arr, k) {
    if(k==0)return []
    if (arr.length < 2) return arr
    let midValue = arr.splice(0, 1), left = [], right = []
    arr.forEach((el) => {
        el > midValue ? left.push(el) : right.push(el)
    });
    if (left.length == k) {
        return left
    } else if (left.length > k) {
        return quickTopK(left, k)
    } else {
        return left.concat(midValue, quickTopK(right, k - left.length - 1))
    }
}
console.log(quickTopK([6, 0, 1, 4, 9, 7, -3, 1, -4, -8, 4, -7, -3, 3, 2, -3, 9, 5, -4, 0], 8))
[ 9, 7, 9, 6, 5, 4, 4, 3]