javascript - JavaScript中的部分排序

有内置的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个最小项的排序列表。

如果您认为其他解决方案可能更快或更优雅,请发布它们。时间非常受欢迎。

最佳答案

否。只有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变量)