Gibt es eine eingebaute JavaScript-Funktion, um ateilweise sortieren? Wenn nicht, was ist ein guter Weg, um es zu implementieren?

Angesichts eines unsortierten Arrays vonN Elemente, die ich gerne finden würdeK Elemente, die in Bezug auf eine Gewichtungsfunktion minimal sind.K ist viel kleiner alsNDaher wäre es ineffizient, das gesamte Array zu sortieren und das erste zu übernehmenK Elemente.

Ich würde mich freuen, auch wenn es etwas nicht standardmäßiges, browserabhängiges gäbe. Ich könnte immer noch auf die benutzerdefinierte JavaScript-Implementierung zurückgreifen.

PS: Dies ist meine derzeitige benutzerdefinierte Implementierung (ohne Berücksichtigung einer Gewichtungsfunktion, nur Sortieren der Elemente, wie sie der Einfachheit halber sind):

function bisect(items, x, lo, hi) {
  var mid;
  if (typeof(lo) == 'undefined') lo = 0;
  if (typeof(hi) == 'undefined') hi = items.length;
  while (lo < hi) {
    mid = Math.floor((lo + hi) / 2);
    if (x < items[mid]) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

function insort(items, x) {
  items.splice(bisect(items, x), 0, x);
}

function partialSort(items, k) {
  var smallest = [];
  for (var i = 0, len = items.length; i < len; ++i) {
    var item = items[i];
    if (smallest.length < k || item < smallest[smallest.length - 1]) {
      insort(smallest, item);
      if (smallest.length > k)
        smallest.splice(k, 1);
    }
  }
  return smallest;
}

console.log(partialSort([5, 4, 3, 2, 1, 6, 7, 8, 1, 9], 3));

Der Algorithmus durchläuft das angegebene Array einmal und verfolgt dabei eine sortierte Liste derk kleinste Elemente bisher, mit binärer Suche, um neue Elemente einzufügen.

Bitte posten Sie alternative Lösungen, wenn Sie glauben, dass sie schneller oder eleganter sind. Timings sind sehr willkommen.