为什么不能在内循环中使用 if 语句而不是插入排序中的 &&？

Question

我想使用此代码进行插入排序，但它给出了未排序的输出：

function insertionSort(arr) {
    //insert each element in the right place in the sorted section
    for (let i=1;i<arr.length;i++) {
        var currentValue = arr[i];
        for (var j=i-1; j>=0; j--) {
            if (arr[j]>currentValue) {
            arr[j+1]=arr[j];
            }
        }
        arr[j+1] = currentValue;
    }
    return arr;
}

正确代码：

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

我就是搞不懂这两个代码在逻辑上的区别。

Answer 1

在 for() 循环中的正确代码 j-- 中停止递减。在你的错误循环中 j-- 继续递减直到 j = -1。因此当你这样做时：

arr[j+1] = currentValue;

在正确的代码中，当 if 条件不再为真时，它将是 j 的最后一个值。

在您的代码中，它总是是：

arr[0] = currentValue;

因为 j 的值总是 -1.

你可以用 break 修复它：

if (arr[j]>currentValue) {
    arr[j+1]=arr[j];
}
else {
    break;
}

Answer 2

在第一个实现中，第二个 for 循环总是运行到结束（直到“j”为 0）。由于您在循环后使用对“j”的引用将“currentValue”写回程序使用了错误的索引。在第二个实现中，当数组中下一个较低的条目不小于时循环停止，因此在循环后引用时将“j”保持在正确的索引处。

出于这个原因，通常不建议在循环外使用迭代器。

为什么不能在内循环中使用 if 语句而不是插入排序中的 &&？

Why can't use an if statement inside of the inner loop instead of && in insertion sort?

javascript

insertion-sort