如何在排序索引位置将元素推入数组？ [英] How can I push an element into array at a sorted index position?
问题描述
说我已经有这些文章的排列，按价格从低到高的顺序排列：
Say I have an array already with these articles, ordered by lowest to highest price:
[
{ title: "Article 3", price: 1.49 },
{ title: "Article 1", price: 3.00 },
{ title: "Article 4", price: 5.99 },
{ title: "Article 2", price: 19.99 }
]
基本上我想将另一件商品按正确位置（按价格）推入阵列。我该怎么做？
Basically I would like to push another article into the array at the correct position (by price). How can I do so?
我要推送的新文章可能具有以下属性：
The new article I'm pushing may have the following properties:
{ title: "Article 5", price: 12.00 }
I我希望该文章出现在索引3（在第4条和第2条之间）。
I'm expecting the article to appear at index 3 (between article 4 and 2).
我使用@klutt的答案和二进制搜索算法创建了一个原型方法：
I created a prototype method using @klutt's answer with binary search algorithm:
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);
推荐答案
如果列表很长，您不会不想每次都对列表进行排序。使用浮点数的排序最多为O（n * log n）。如果您进行线性搜索，则会得到O（n）。
If it is a very long list, you don't want to sort the list everytime. A sorting with floats is at best O(n*log n). If you do a linear search you will have O(n) instead.
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）。二进制搜索非常简单。您从中间开始。如果该元素大于要搜索的元素，则对列表的上半部分应用相同的算法，否则对下半部分应用。在网络上很容易找到二进制搜索的代码示例。
However, if the list is VERY long it would be a good idea to do a binary search instead of a linear search. That would take it down to O(log n). A binary search is pretty simple. You start in the middle. If the element is larger than what you're searching for, apply the same algorithm to the upper half of the list, otherwise to lower part. It's easy to find code examples of binary search on the web.
这里是一个示例：
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)
（从这里被盗用Javascript进行二进制搜索）
但要总结一下。添加元素然后进行排序通常是一个坏主意。最好的情况是，这无关紧要，但是既然您知道列表是排序的，为什么不至少要进行线性搜索呢？
But to wrap it up. Adding the element and then sorting is usually a bad idea. Best case is that it does not matter, but since you know that the list is sorted, why not do at least a linear search?
如果列表很小，这没关系，但是如果列表中有数百万个元素，差异将非常明显。
If the lists are small, this does not matter, but if the lists have millions of elements the difference will be quite noticeable.
编辑：
我建立了一个快速而原始的基准。
I made a quick and primitive benchmark.
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
我测量了在四种不同大小上运行这三种算法所需的时间。我不想等待排序结束于一千万个元素上。因此，不适用。时间以毫秒为单位。请注意，基准测试是非常原始的，但是它提供了有关大小增长时会产生多大影响的想法。
I measured the time it took to run the three algorithms on four different sizes. I did not want to wait for the sorting to end on ten million elements. Therefore the N/A. Time is in milliseconds. Note that the benchmark were very primitive, but it gives an idea about how much it affects when sizes grow.
这篇关于如何在排序索引位置将元素推入数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
