JavaScript版「剣指offer」ブラシ問題(28)最小K個数

1.テーマの説明
n個の整数を入力して、一番小さいK個の数を探します.例えば4,5,1,6,2,7,3,8という8つの数字を入力すると、最小の4つの数字は1,2,3,4です.
2.テーマ分析
この問題には三つの方法があります.
考え方の1:まず並べ替えて、それから最小のを探し出しています.しかし、配列が大きいかもしれません.タイムアウトします.
考え方その2:快速秩序化の原理を利用して問題を解決する.配列のk個の数字に基づいて調整され、k番目の数字より小さい数字はすべてその左側に位置し、k番目の数字より大きい数字は全て配列の右側に位置し、調整後、配列の左に位置するk個の数字は最小のk個の数字である(このk個の数字は必ずしも並べ替えではない).
考え方3:長さKの配列を利用して、k個の現在最小の数を保存して、その後毎回中の最大値と現在値を見つけて比較します.
3.コード
考え方の一つのコード:

function GetLeastNumbers_Solution(input, k)
{
    if(input.length < k) return false;
    input.sort(function(a,b){return a-b;});
    return input.slice(0,k);
}

構想二コード:

//        
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function partation(arr, start, end) {
    var pivot = arr[end]; //    
    var i = start; //     +1            
    for (var j = start; j < end; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, end);
    return i;
}

function GetLeastNumbers_Solution(input, k) {
    var result = [];
    if (input.length < 0 || k > input.length || k <= 0) {
        return false;
    }
    var start = 0;
    var end = input.length - 1;
    var p = partation(input, start, end);
    while (p !== (k - 1)) {
        if (p > (k - 1)) {
            end = p - 1;
            p = partation(input, start, end);
        } else {
            start = p + 1;
            partation(input, start, end);
        }
    }
    for (var i = 0; i < k; i++) {
        result.push(input[i]);
    }
    return result;
}

考え方3コード:

function getLeastNums(array, k) {
    let len = array.length;
    if(k > len) {
        return false;
    }
    let arr = array.slice(0, k),
        maxIndex = findMaxIndex(arr),
        max = arr[maxIndex];
    for(let i=k; i a - b);
}
function findMaxIndex(arr) {
    let max = arr[0],
        index = 0;
    for(let i=1,len=arr.length; i

参考記事:https://www.cnblogs.com/echovic/p/6558985.html https://www.cnblogs.com/wuguanglin/p/GetLeastNumbers_Solutions.https://github.com/DavidChen93/-offer-JS-/blob/master/40.1%20%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0.js
クイックソート思想partiotionに基づいてK番目の大きい数またはK番目の小さい数を検索します.https://www.cnblogs.com/wuguanglin/p/searchKMax.html