冒泡排序 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]

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

Answer 2

考虑数组（按升序排序）：

[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 中的所有项目都按排序顺序排列，因此不需要re-sort/re-check 他们。

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

Answer 3

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

Answer 4

减号 i 是为了说明这样一个事实，即在您第一次对数组进行完整迭代后，最右边的元素将位于正确的位置。因此，您以后不必再尝试 re-sort 了。这就是为什么你在那里有负号 i 的原因。

冒泡排序 javascript 代码几乎不需要解释

Bubble sort javascript code need explanation little

javascript

bubble-sort