javascript - 插入排序对象数组

Question

我有一个几乎排序的〜1000个对象的数组，例如{val: N}并通过内置对它们进行排序Array.prototype.sort：

arr.sort(function(a, b) { return a.val - b.val });

我偶然发现了http://jsperf.com/javascript-sort/16并尝试使用插入排序：

for (i = 1; i < arr.length; i++) {
    var tmp = arr[i],
    j = i;
    while (arr[j-1].val > tmp.val) {
        arr[j] = arr[j-1];
        --j;
    }
    arr[j] = tmp;
}

但它总是抛出一个错误：TypeError: Cannot read property 'kills' of undefined.

在哪里挖？

提前致谢。

Answer 1

您在循环中缺少对 j 的边界检查：

while (j > 0 && arr[j-1].val > tmp.val) {
    arr[j] = arr[j-1];
    --j;
}