javascript - 如何将元素插入数组中已排序的索引位置？

Question

假设我已经有了一个包含这些文章的数组，按从低到高的价格排序:

[
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

基本上我想在正确的位置(按价格)将另一篇文章插入数组。我该怎么做？

我推送的新文章可能具有以下属性:

{ title: "Article 5", price: 12.00 }

我希望这篇文章出现在索引 3(第 4 条和第 2 条之间)。

更新(解决方案)

我使用@klutt's answer with binary search algorithm 创建了一个原型(prototype)方法:

Array.prototype.pushSorted = function(el, compareFn) {
  this.splice((function(arr) {
    var m = 0;
    var n = arr.length - 1;

    while(m <= n) {
      var k = (n + m) >> 1;
      var cmp = compareFn(el, arr[k]);

      if(cmp > 0) m = k + 1;
        else if(cmp < 0) n = k - 1;
        else return k;
    }

    return -m - 1;
  })(this), 0, el);

  return this.length;
};

const sortByPrice = (a, b) => a.price > b.price;
theArray.pushSorted({ title: "Article 5", price: 12.00 }, sortByPrice);

Answer 1

如果它是一个很长的列表，你不想每次都对列表​​进行排序。用 float 排序最多是 O(n*log n)。如果您进行线性搜索，您将得到 O(n)。

function search(a, v) {
    if(a[0]['price'] > v['price']) {
        return 0;
    }
    var i=1;
    while (i<a.length && !(a[i]['price'] > v['price'] && a[i-1]['price'] <= v['price'])) {
        i=i+1;
        }
    return i;
}

myArray.splice(search(myArray, newItem), 0, newItem)

但是，如果列表很长，最好进行二分搜索而不是线性搜索。这会将它降低到 O(log n)。二分查找非常简单。你从中间开始。如果该元素大于您要搜索的元素，则将相同的算法应用于列表的上半部分，否则应用于下半部分。在网络上很容易找到二分查找的代码示例。

这是一个例子:

function binarySearch(ar, el, compare_fn) {
    if (el.price < ar[0].price)
        return 0;
    if (el.price > ar[ar.length-1].price)
        return ar.length;
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

function comp(a, b) {
    return a['price']>b['price']
}

myArray.splice(binarySearch(myArray, element, comp), 0, element)

(从这里偷来的 Binary Search in Javascript )

但要把它包起来。添加元素然后排序通常不是一个好主意。最好的情况是这无关紧要，但既然您知道列表已排序，为什么不至少进行一次线性搜索？

如果列表很小，这无关紧要，但如果列表有数百万个元素，差异就会非常明显。

编辑:

我做了一个快速而原始的基准测试。

            10,000   100,000  1000,000   10,000,000  
Sort            80       900     13000          N/A
Linear           2         2        25         5000
Binary           2         2         5           21

我测量了在四种不同尺寸上运行三种算法所花费的时间。我不想等待排序结束一千万个元素。因此 N/A。时间以毫秒为单位。请注意，该基准测试非常原始，但它给出了尺寸增长时它会产生多大影响的想法。