将数字插入到已排序的数字数组中的有效方法? [英] Efficient way to insert a number into a sorted array of numbers?

问题描述

我有一个已排序的 JavaScript 数组，我想在数组中再插入一项，这样结果数组就会保持排序.我当然可以实现一个简单的快速排序风格的插入功能:

I have a sorted JavaScript array, and want to insert one more item into the array such the resulting array remains sorted. I could certainly implement a simple quicksort-style insertion function:

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

[警告] 这段代码在尝试插入到数组的开头时有一个错误，例如insert(2, [3, 7 ,9]) 产生不正确的 [ 3, 2, 7, 9 ].

[WARNING] this code has a bug when trying to insert to the beginning of the array, e.g. insert(2, [3, 7 ,9]) produces incorrect [ 3, 2, 7, 9 ].

但是，我注意到 Array.sort 函数的实现可能会为我做这件事，而且是本机:

However, I noticed that implementations of the Array.sort function might potentially do this for me, and natively:

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

选择第一个实现而不是第二个实现有充分的理由吗?

Is there a good reason to choose the first implementation over the second?

编辑:请注意，对于一般情况，O(log(n)) 插入(如第一个示例中实现的)将比通用排序算法更快；然而，对于 JavaScript 而言，情况并非一定如此.请注意:

Edit: Note that for the general case, an O(log(n)) insertion (as implemented in the first example) will be faster than a generic sorting algorithm; however this is not necessarily the case for JavaScript in particular. Note that:

• 几种插入算法的最佳情况是 O(n)，它仍然与 O(log(n)) 显着不同，但并不像下面提到的 O(n log(n)) 那样糟糕.这将归结为使用的特定排序算法(参见 Javascript Array.sort 实现?)
• JavaScript 中的 sort 方法是一个本机函数，因此可能会实现巨大的好处——对于合理大小的数据集，具有巨大系数的 O(log(n)) 仍然比 O(n) 差很多.

推荐答案

作为一个单一的数据点，我测试了使用 Chrome 上的两种方法将 1000 个随机元素插入到 100,000 个预排序数字的数组中视窗 7:

Just as a single data point, for kicks I tested this out inserting 1000 random elements into an array of 100,000 pre-sorted numbers using the two methods using Chrome on Windows 7:

First Method:
~54 milliseconds
Second Method:
~57 seconds

所以，至少在这个设置上，本地方法并不能弥补它.即使对于小数据集也是如此，将 100 个元素插入到 1000 个数组中:

So, at least on this setup, the native method doesn't make up for it. This is true even for small data sets, inserting 100 elements into an array of 1000:

First Method:
1 milliseconds
Second Method:
34 milliseconds

这篇关于将数字插入到已排序的数字数组中的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！