冒泡排序javascript代码需要解释一点

Question

我正在写一个有趣的泡泡排序程序，但我不明白的是j<len-i在这段代码中做了什么？

我可以从上面的行中删除-i它也可以工作，

var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

var len = arr.length,
    i, j, stop;

for (i=0; i < len; i++){
    for (j=0; j<len-i;  j++){
        if (arr[j] > arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;

        }
    }
}

return arr;
}
console.log(bubble_Sort(arr));

//with -i in second for loop
var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

    var len = arr.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0; j<len-i;  j++){
            if (arr[j] > arr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                
            }
        }
    }

    return arr;
}
console.log(bubble_Sort(arr));

在第二个循环中没有-i

Answer 1

如果你为每个“i”循环记录arr，你就会明白为什么会这样。

var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

var len = arr.length,
    i, j, stop;

for (i=0; i < len; i++){
    for (j=0; j<len-i;  j++){
        if (arr[j] > arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;

        }
    }
    console.log(arr)
}

return arr;
}
console.log(bubble_Sort(arr));

(9) [3, 4, 5, 7, 8, 9, 0, -1, 30]

(9) [3, 4, 5, 7, 8, 0, -1, 9, 30]

(9) [3, 4, 5, 7, 0, -1, 8, 9, 30]

(9) [3, 4, 5, 0, -1, 7, 8, 9, 30]

(9) [3, 4, 0, -1, 5, 7, 8, 9, 30]

(9) [3, 0, -1, 4, 5, 7, 8, 9, 30]

(9) [0, -1, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

每个i循环，它将第i个大数移动到底部，所以最后一个i数是稳定的。

Answer 2

这是因为每次最后一个元素都被排序。在每次迭代之后，您会发现最后一个元素位于正确的位置（第0次迭代 - 最后一个元素位于正确位置，第一次迭代 - 最后2个元素位于正确位置，依此类推）。所以每次我们遍历len-i元素。

Answer 3

考虑数组（按递增顺序排序）：

[4, 3, 2, 1]

使用i = 0运行内循环后，您将获得：

[3, 2, 1, 4]

现在，i=1 ......

再次重复这个过程，在下一次迭代时，你会得到i=1：

[2, 1, 3, 4]

现在，i=2

再次，在i=2再次重复循环，你得到：

[1, 2, 3, 4]

现在i=3

请注意粗体数字是如何排序的。

这里我们有一个用于外部循环的loop invariant（即一个对外部循环的每次迭代都成立的语句），这是数组的最后一个i项目按排序顺序排列。或者，另一种看待它的方法是来自[0, ... length-i)的数组中的所有项目都没有排序，因此来自索引length-i及其后的项目按排序顺序排列。

换句话说，当您查看数组时，您可以看到在外循环的每次迭代之后，数组中来自length-i, ..., length的所有项都按排序顺序排列，因此无需重新排序/重新检查它们。

因此，提供len-i可以防止您按已排序的顺序重新检查项目，因为您知道它们不需要更改。