为什么我们在冒泡排序算法的内循环中使用`length-i-1`

Question

使用javascript，它被编程为按asc顺序对数组中的元素进行排序。我尽力理解为什么内循环使用 length-i-1，但不能。谁能帮我理解我们为什么要使用它？

function bubbleSort(arr) {

    for(let i=0; i<= arr.length; i++) {
        for(let j=0; j< arr.length-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                let lesser = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = lesser;
            }
        }
    }

    return arr;
}

Answer 1

正如 Daniel 在他的评论中所说，这是因为这些项目已经排序（例如，在第一次迭代中以最高索引结束的最大元素）

看下面的gif，注意8是怎么在最右边结束的，然后被黑框包围了，表示不需要再移动了，所以不需要勾选不再（它大于 length-i-1）。

不检查这些已经 'locked in' 的元素有助于提高算法速度。

Gif 来自：Bubble Sort on Wikipedia

Answer 2

我们分步骤来想一下：举例来说，假设您有一个包含 10 个元素的数组。

第一步

i = 0, j goes from 0 to 9( = 10 - 0 - 1)

所以遍历了整个数组。现在，每次当前元素大于下一个元素时，我们都会切换它们（按 if(arr[j] > arr[j+1])），因此在第一次迭代结束时，在最后一个位置我们将拥有最大元素大批。

第二步

i = 1, j goes from 0 to 8( = 10 - 1 - 1)

现在，我们可以注意到我们遗漏了最后一个（第 9 个）位置，但我们知道它已经是上一步的最大值，所以它处于正确的位置。在本次迭代结束时，我们将在第 8 个位置获得第 2 个最大元素，并且该过程继续..

Answer 3

编辑：Phone 太慢了：P

在每次外部迭代之后，第 i 个最大的元素位于正确的位置。因此，在第一次迭代之后，最大的元素位于最右侧。既然我们知道了，我们就不必在下一轮比较这个元素了。在第二次 Iteration 之后，第二大的元素在最右边的 Side -1 位置。所以最大的两个元素已经排序好了，下一轮就不用考虑了。

用一个简单的例子来尝试你的算法，然后手动逐步完成。那你应该看清楚了。

为什么我们在冒泡排序算法的内循环中使用`length-i-1`

Why do we use `length-i-1` in the inner loop of bubble sort algorithm

javascript

algorithm

bubble-sort