将数字插入有序数组的有效方法？
我有一个已排序的 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));
这段代码在尝试插入到数组的开头时有一个 bug，例如 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 中的 sort 方法是一个本机函数，因此对于合理大小的数据集，具有巨大系数的 O (log (n))仍然比 O (n)糟糕得多。
最佳答案