如何保持 Javascript 数组排序，而不对其进行排序

How to keep Javascript array sorted, without sorting it

提问by Juha-Matti Hurnasti

I have a Node.js application where I have to very often do following things: - check if particular array already contains certain element - if element does exist, update it - if element do not exist, push it to the array and then sort it using underscore _.sortBy

我有一个 Node.js 应用程序，我必须经常做以下事情： - 检查特定数组是否已经包含某个元素 - 如果元素确实存在，更新它 - 如果元素不存在，将其推送到数组然后对其进行排序使用下划线 _.sortBy

For checking if the element already exists in the array, I use this binary search function: http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

为了检查元素是否已经存在于数组中，我使用了这个二进制搜索函数：http: //oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

In this way, when the size of the array grows, the sorting becomes slower and slower. I assume that the array size might grow to max 20 000 items per user. And eventually there will be thousands of users. The array is sorted by a key, which is quite a short string. It can be converted into integer if needed.

这样，当数组的大小增长时，排序变得越来越慢。我假设数组大小可能会增长到每个用户最多 20 000 个项目。最终将有成千上万的用户。该数组按一个键排序，键是一个很短的字符串。如果需要，它可以转换为整数。

So, I would require a better way to keep the array sorted, in stead of sorting it every time new element is pushed onto it.

因此，我需要一种更好的方法来保持数组排序，而不是每次将新元素推送到数组时对其进行排序。

So, my question is, how should/could I edit the binary search algorithm I use, to enable me to get the array index where the new element should be placed, if it doesn't already exist in the array? Or what other possibilities there would be to achieve this. Of course, I could use some kind of loop that would start from the beginning and go through the array until it would find the place for the new element.

所以，我的问题是，如果新元素不存在于数组中，我应该/如何编辑我使用的二分搜索算法，以使我能够获取应放置新元素的数组索引？或者还有什么其他可能性可以实现这一目标。当然，我可以使用某种循环，从头开始遍历数组，直到找到新元素的位置。

All the data is stored in MongoDB.

所有数据都存储在 MongoDB 中。

In other words, I would like to keep the array sorted without sorting it every time a new element is pushed.

换句话说，我想保持数组排序，而不是每次推送新元素时对其进行排序。

回答by Leonid Beschastny

It's easy to modify this binaryIndexOffunction to return an index of the next element when no matches found:

修改此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
  };
}

So, now it returns objects like:

所以，现在它返回如下对象：

{found: false, index: 4}

where indexis an index of the found element, or the next one.

whereindex是找到的元素的索引，或者下一个。

So, now insertion of a new element will look like:

所以，现在插入一个新元素将如下所示：

var res = binaryFind.call(arr, element);
if (!res.found) arr.splice(res.index, 0, element);

Now you may add binaryFindto Array.prototypealong with some helper for adding new elements:

现在，您可以添加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);
}

回答by Tibos

If your array is already sorted and you want to insert an element, to keep it sorted you need to insert it at a specific place in the array. Luckily arrays have a method that can do that: Array.prototype.splice

如果您的数组已经排序并且您想插入一个元素，为了保持排序，您需要将其插入数组中的特定位置。幸运的是，数组有一个方法可以做到这一点： Array.prototype.splice

So, once you get the index you need to insert at (you should get by a simple modification to your binary search), you can do:

因此，一旦您获得需要插入的索引（您应该通过对二进制搜索进行简单修改来获得），您可以执行以下操作：

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

EDIT: The author of your binary search code has the same idea:

编辑：您的二进制搜索代码的作者有相同的想法：

So if you wanted to insert a value and wanted to know where you should put it, you could run the function and use the returned number to splice the value into the array. Source

因此，如果您想插入一个值并想知道应该把它放在哪里，您可以运行该函数并使用返回的数字将值拼接到数组中。 来源

回答by Brad

I know this is an answer to an old question, but the following is very simple using javascripts array.splice().

我知道这是一个老问题的答案，但以下使用 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
}

The order can be changed to high to low by inverting the test

可以通过反转测试来改变顺序