最小的 k 个元素--快排变形

利用快速排序分割序列的思路，不断分割数组即可

function devide(a, l, r, k)
{
    if(r - l + 1 == k) return a.slice(l,  r + 1);
    let pivot = a[l];
    let i = l;
    let j = r;

    while(i < j){
        while(i < j && a[j] > pivot) j--;
        if(i < j){
            a[i] = a[j];
            i++;
        }

        while(i < j && a[i] < pivot) i++;
        if(i < j){
            a[j] = a[i];
            j--;
        }
    }

    a[i] = pivot;

    if(i - l + 1 === k){
        return a.slice(l, i + 1);
    }else if(i - l + 1 > k){
        return devide(a, l, i - 1, k);
    }else{
        return a.slice(l, i + 1).concat(devide(a, i + 1, r, k - (i - l + 1)));
    }
}

let a = [1, -1, 3, 7, 0, 10];
console.log(devide(a, 0, a.length - 1, 1));

本作品采用《CC 协议》，转载必须注明作者和本文链接