如何保持Javascript数组sorting，没有sorting
我有一个Node.js应用程序，我必须经常做以下事情： – 检查特定的数组是否已经包含某个元素 – 如果元素确实存在，更新它 – 如果元素不存在，将其推入数组，然后对其进行sorting使用下划线_.sortBy
为了检查数组是否已经存在，我使用这个二进制search函数： http : //oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/
这样，当数组的大小增长时，sorting变得越来越慢。 我假设arrays大小可能增长到每个用户最多20,000个项目。 最终会有成千上万的用户。 该数组是通过一个非常短的string键来sorting的。 如果需要，可以将其转换为整数。
所以，我需要一个更好的方法来保持数组的sorting，而不是每次将新元素推到它时进行sorting。
所以，我的问题是，如果编辑我使用的二进制searchalgorithm，我该如何编辑这个二进制searchalgorithm，以使我能够在新元素应该被放置的地方得到数组索引，如果它不在数组中？ 或者有什么其他的可能性来实现这一点。 当然，我可以使用某种循环，从头开始，遍历数组，直到find新元素的位置。
所有的数据存储在MongoDB中。
换句话说，我想保持数组sorting，而不是每次推新元素时都进行sorting。
修改这个binaryIndexOf函数很容易，当找不到匹配的时候返回下一个元素的索引：
function binaryFind(searchElement) { 'use strict'; var minIndex = 0; var maxIndex = this.length - 1; var currentIndex; var currentElement; while (minIndex <= maxIndex) { currentIndex = (minIndex + maxIndex) / 2 | 0; currentElement = this[currentIndex]; if (currentElement < searchElement) { minIndex = currentIndex + 1; } else if (currentElement > searchElement) { maxIndex = currentIndex - 1; } else { return { // Modification found: true, index: currentIndex }; } } return { // Modification found: false, index: currentElement < searchElement ? currentIndex + 1 : currentIndex }; }
所以，现在它返回像这样的对象：
{found: false, index: 4}
其中index是find的元素或下一个元素的索引。
所以，现在插入一个新的元素将如下所示：
var res = binaryFind.call(arr, element); if (!res.found) arr.splice(res.index, 0, element);
现在你可以添加binaryFind到Array.prototype以及一些帮助器来添加新的元素：
Array.prototype.binaryFind = binaryFind; Array.prototype.addSorted = function(element) { var res = this.binaryFind(element); if (!res.found) this.splice(res.index, 0, element); }
如果您的数组已经sorting并且您想要插入一个元素，为了保持sorting，您需要将其插入到数组中的特定位置。 幸运的是，数组有一个方法可以做到这一点： Array.prototype.splice
所以，一旦你得到索引你需要插入（你应该得到一个简单的修改你的二进制search），你可以这样做：
myArr.splice(myIndex,0,myObj); // myArr your sorted array // myIndex the index of the first item larger than the one you want to insert // myObj the item you want to insert
编辑：你的二进制search代码的作者有相同的想法：
所以，如果你想插入一个值，并想知道你应该把它放在哪里，你可以运行该函数，并使用返回的数字将值拼接到数组中。 资源
我知道这是一个老问题的答案，但使用javascripts array.splice（），以下是非常简单的。
function inOrder(arr, item) { /* Insert item into arr keeping low to high order */ let ix = 0; while (ix < arr.length) { //console.log('ix',ix); if (item < arr[ix]) { break; } ix++; } //console.log(' insert:', item, 'at:',ix); arr.splice(ix,0,item); return arr }
通过反转testing，可以将订单从高到低更改