javascript - 插入排序循环不变量

Question

function insertionSort(arr)  {
var length = arr.length,
val,
i,
j;
for(i = 0; i < length; i++) {
    value  = arr[i];
    for(j = i - 1; j > -1 && arr[j] > value; j--) {
        arr[j+1] = arr[j]
    }
    arr[j+1] = value;
}
return arr;

}

控制台日志（插入排序（[6,1,23,4,2,3]））

---

我正在查看一个用 javascript 编码的插入排序算法的示例，并且无法理解为什么它会通过内部 for 循环的条件。需要明确的是，这个算法是正确的——我只是很难理解为什么。

如果 j 用 i - 1 初始化，那么 j 的值为 -1，因为 i 被初始化为 0。在条件的第一部分，它声明 j > -1，这意味着它不会通过这个测试，因为 j 不大于 -1。

有人能告诉我我错过了什么吗？

标签： javascriptalgorithmsorting

Answer 1

你是对的，第一次迭代不会进入第二次循环，但这没关系。注意那个循环在做什么。array[j+1]它正在与交换array[j]。什么时候i == 0，那么j == -1。您不能array[0]与交换array[-1]，因为它不存在。这是绕过该问题的巧妙方法。

但是，这只发生在第一次迭代中。随后的迭代将按预期进入循环。