java - 当找到前 n 个值时如何停止冒泡排序？

Question

我目前正在学习 Java，我有一个关于冒泡排序的问题要问。

假设我有一个名为 array 的数字数组，我使用冒泡排序对其进行排序。

int[] array = {10, 22, 30, 50, 11, 22, 80, 66, 55, 32};

        for (int i = 0; i < b; i++) {
            for (int j = 0; j < array.length - 1 -i; j++) {
                  if (array[j + 1] < array[j]) {
                    int temp;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }

我的目标是找到列表中最大的 n 个值，并一旦找到 n 个最大值就停止排序。如果变量 b 是它需要比较某个值的次数。 n 与 b 有何关系？

在这种特殊情况下，如果 n = 3 那么它应该停在箭头所在的位置。 在每个步骤中，输出为:

[10, 22, 30, 50, 11, 22, 80, 66, 55, 32]
[10, 22, 30, 50, 11, 22, 80, 66, 55, 32]
[10, 22, 30, 50, 11, 22, 80, 66, 55, 32]
[10, 22, 30, 11, 50, 22, 80, 66, 55, 32]
[10, 22, 30, 11, 22, 50, 80, 66, 55, 32]
[10, 22, 30, 11, 22, 50, 80, 66, 55, 32]
[10, 22, 30, 11, 22, 50, 66, 80, 55, 32]
[10, 22, 30, 11, 22, 50, 66, 55, 80, 32]
[10, 22, 30, 11, 22, 50, 66, 55, 32, 80]
[10, 22, 30, 11, 22, 50, 66, 55, 32, 80]
[10, 22, 30, 11, 22, 50, 66, 55, 32, 80]
[10, 22, 11, 30, 22, 50, 66, 55, 32, 80]
[10, 22, 11, 22, 30, 50, 66, 55, 32, 80]
[10, 22, 11, 22, 30, 50, 66, 55, 32, 80]
[10, 22, 11, 22, 30, 50, 66, 55, 32, 80]
[10, 22, 11, 22, 30, 50, 55, 66, 32, 80]
[10, 22, 11, 22, 30, 50, 55, 32, 66, 80]
[10, 22, 11, 22, 30, 50, 55, 32, 66, 80]
[10, 22, 11, 22, 30, 50, 55, 32, 66, 80]
[10, 11, 22, 22, 30, 50, 55, 32, 66, 80]
[10, 11, 22, 22, 30, 50, 55, 32, 66, 80]
[10, 11, 22, 22, 30, 50, 55, 32, 66, 80]
[10, 11, 22, 22, 30, 50, 55, 32, 66, 80]
[10, 11, 22, 22, 30, 50, 55, 32, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80] <--- where the sorting should stop ( 3 largest value found )
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 50, 32, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]
[10, 11, 22, 22, 30, 32, 50, 55, 66, 80]

Answer 1

In bubble sort:

n-th pass finds the n-th largest element and puts it into its final place

所以在你的代码中，如果你想找到最大的n个项目，你应该设置b等于n。当外循环退出时，数组中的最后n项将是n个最大值。

编辑(回应评论):

上述定义中的“pass”一词指的是外循环运行的次数。如果没有有关数组的信息，则很难确定内部循环的确切迭代次数。举个例子:

[1, 2, 3, 4]

这已经排序了。如果b = 2，则经过两次传递后，保证最后两个元素是最大的(3和4)。但程序连内循环都没有进入。现在，如果这是数组:

[4, 3, 2, 1]

再次经过两次之后，我们将得到:

[2, 1, 3, 4]

不同的是，内循环分别迭代了3次和2次，将3和4放在数组的尾部。对于完全反向排序的数组，内部循环将执行总计:

(n - 1) + (n - 2) + ... + 1

迭代。