javascript - JavaScript 中的部分排序

Question

是否有任何内置的 JavaScript 函数来执行 partial sort ？如果不是，什么是实现它的好方法？

给定一个未排序的 N 元素数组，我想找到 K 个元素，这些元素相对于某些加权函数而言是最小的。 K 远小于 N，因此对整个数组进行排序并取前 K 个元素效率不高。

即使有一些非标准的、依赖于浏览器的东西，我也会很高兴。我仍然可以回退到自定义 JavaScript 实现。

PS:这是我目前的自定义实现(没有考虑权重函数，为了简单起见，只是按原样对元素进行排序):

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));

该算法一次性遍历给定数组，跟踪到目前为止 k 最小项的排序列表，使用二进制搜索插入新元素。

如果您认为它们可能更快或更优雅，请发布替代解决方案。时间安排非常受欢迎。

Answer 1

没有。只有 full array sort ，因此您需要使用自己的实现。

您的代码略有改进(我想到了完全相同的算法:-)):

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

(即使是 seems to be a little faster，我猜是由于缓存了 max 变量)