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

Question

冒泡排序算法最常见的方式是有两个for循环。内一从 j=0 直到 j n-i-1 完成。我假设我们减去 i，因为当我们到达最后一个元素时我们不比较它，因为我们在他之后没有元素。但是为什么我们使用n-1。为什么我们不运行从 i=0 到 i < n 的外部循环和从 j=0 到 n-i 的内部循环？谁能给我解释一下，网上的教程都不强调这个。

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 次比较等的数组中：

array and comparisons between adjacent cells

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

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

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

在第一个循环 (i = 0) 之后，20 已到达其在数组中的正确位置（使用升序），留给我们一个包含 3 个元素的数组比较;在下一个循环中，i 将等于 1，由于 n-1 保持不变，我们需要将表达式中的 1 减去 "shorten" 数组： n-1-i = 4-1-1 = 2，这是新数组中最后一个元素的索引以及需要比较的数量。

希望对您有所帮助！

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

Why do we make n-1 iterations in bubble sort algorithm

c++

sorting

bubble-sort