为什么我们在冒泡排序算法中进行n-1次迭代

Question

泡泡排序算法最常见的方法是有两个for循环.内部一个从j = 0到j ni-1完成.我假设我们减去负i,因为当我们到达最后一个元素时,我们不比较它,因为我们之后没有一个元素.但为什么我们使用n-1.为什么我们不从i = 0运行外循环直到i <n并且从j = 0到ni？有人可以向我解释一下,互联网上的教程并没有强调这一点.

for (int i = 0; i < n - 1; i++) // Why do we have n-1 here?
    {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            countComparisons++;
            if (arr[j] > arr[j + 1])
            {
                countSwaps++;
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }

        }
     }

例如,如果我有一个包含6个元素的数组,为什么我只需要进行5次迭代？

Answer 1

因为交换需要至少两个元素.

因此,如果您有6个元素,则只需要考虑5个连续对.

Answer 2

为了在数组中进行比较，需要两个相邻的单元格；在 6 个元素的数组中，您只进行 5 次比较；在包含 10 个元素、9 个比较等的数组中：

数组和相邻单元格之间的比较

所以对于 7 个元素，只进行了 6 次比较，因此外部for循环中 n-1 的一般规则

关于n-1-i表达式，请记住冒泡排序中的最高（或最低，取决于排序标准）值在第一个循环后到达数组中的最后位置，因此无需比较该值与其他任何东西一样，因此数组必须一次“缩短”1 个单元格，并且外循环中i的值是负责内循环中的计数器：

5 | 3 | 9 | 20 | 元素 (n) = 4

在第一个循环 ( i = 0 ) 之后， 20 已到达数组中的正确位置（使用升序），留下一个包含 3 个元素的数组来进行比较；在下一个循环中，i将等于 1，并且由于 n-1 保持不变，我们需要在该表达式中减去 1 以“缩短”数组：n-1-i = 4-1-1 = 2，即是该新数组中最后一个元素的索引以及所需的比较数量。

希望能帮助到你！