我有一个已排序的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 implementation?）。
- JavaScript中的sort方法是本地函数，因此可能会产生巨大的好处--具有巨大系数的O(log(n))可能仍然比适度大小的数据集的O(n)要糟糕得多。
splice()的内容（例如您的第一个示例）已经是O(n)。 即使它在内部不创建整个数组的新副本，如果要将元素插入到位置0，则可能必须将所有n个项都向后移动1个位置。 也许它之所以快速是因为它是原生函数且常量很低，但无论如何它仍然是O(n)。 - j_random_hackerparseInt，应该使用Math.floor代替。Math.floor比parseInt更快：https://jsperf.com/test-parseint-and-math-floor - Hubert Schölnast