java - 如果冒泡排序的第一遍将最小的气泡放在第 0 个位置是对的吗？

Question

从 GeeksforGeeks 我找到了这个定义:

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Example:

First Pass:( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.Second Pass:( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

如果我按照从 n-1 到 0 的相反顺序执行此操作会怎样？这是正确的吗，因为我在第一次通过时将阵列的最小气泡放在第一个位置。

我的代码是这样写的:

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

Answer 1

是的，您的代码会起作用。

但是为了在速度方面提高程序效率，您应该更改第二个 for 循环中的条件。正如你所写的

for (int j = array.length - 1; j > 0; j--) {
    ...
}

这里，在Second Pass中，当j的值为1时，它会不必要地检查这个条件

array[j - 1] > array[j]

因为，在第一遍之后，array[0] 已经是最小的了。因此，您无需再次检查。

而在第三遍，会出现两个不必要的条件等等等等。

因此，我建议您使用j > i 作为第二个for 循环的条件。那么你的整行将是

for (int j = array.length - 1; j > i; j--) {
    ...
}