有效的方式插入一个数字，数字的排序的数组？ [英] 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));

不过，我注意到的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（日志（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（日志（N）），但没有那么糟糕，因为O（N日志（N））如下所述。这将归结为使用的特定排序算法（参见 Javascript的执行的Array.sort ？）
• 在JavaScript中的排序方法是一个本机的功能，所以有可能实现巨大的好处 - 为O（log（n））的一个巨大的系数仍然可以比O（n）的差多少为合理大小的数据集。

推荐答案

只是作为一个单一的数据点，踢我测试了这一点插入1000的随机元素融入到100,000 pre排序数字数组使用这两种方法使用Chrome浏览器在Windows 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屋！