将数字插入到排序的数字数组中的有效方法？

javascript algorithm sorting

2022-08-30 01:42:08

我有一个排序的JavaScript数组，并希望在数组中插入另一个项目，这样结果数组仍然保持排序状态。我当然可以实现一个简单的快速排序样式插入函数：

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 ]。

但是，我注意到 Array.sort 函数的实现可能会为我执行此操作，并且本身：

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));

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

编辑：请注意，对于一般情况，O（log（n））插入（如第一个示例中实现的）将比通用排序算法更快;然而，对于JavaScript来说，情况并不一定如此。请注意：

几种插入算法的最佳情况是O（n），它仍然与O（log（n））有显着不同，但并不像下面提到的O（n log（n））那么糟糕。它将归结为使用的特定排序算法（请参阅Javascript Array.sort实现？)
JavaScript中的排序方法是一个原生函数，因此潜在地实现巨大的好处 - 对于合理大小的数据集，具有巨大系数的O（log（n））仍然比O（n）差得多。

答案 1

简单（演示）：

function sortedIndex(array, value) {
    var low = 0,
        high = array.length;

    while (low < high) {
        var mid = (low + high) >>> 1;
        if (array[mid] < value) low = mid + 1;
        else high = mid;
    }
    return low;
}

答案 2

就像一个单一的数据点一样，对于踢，我测试了这一点，使用Windows 7上使用Chrome的两种方法将1000个随机元素插入到100，000个预先排序的数字数组中：

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

因此，至少在此设置上，本机方法无法弥补它。即使对于小数据集也是如此，将 100 个元素插入到 1000 个数组中：

First Method:
1 milliseconds
Second Method:
34 milliseconds