javascript - 将数字插入已排序的数字数组的有效方法？

Question

我有一个已排序的 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));

[WARNING] 此代码在尝试插入数组开头时存在错误，例如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 implementation? )
• JavaScript 中的 sort 方法是一个原生函数，因此有可能实现巨大的好处——具有巨大系数的 O(log(n)) 对于合理大小的数据集来说仍然比 O(n) 差得多。

Answer 1

简单(Demo):

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