JavaScript中的部分排序

Question

是否有任何内置的JavaScript函数可以进行局部排序？如果没有,实施它的好方法是什么？

给定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

没有.只有完整的数组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;
}

(甚至似乎更快一点,我想由于缓存max变量)