创建了几乎可以工作的排序算法，但我不明白第二个 for 循环

Question

这是我自己编写的代码，我理解这里所做的一切：

import java.util.Arrays;
public class Decision{
    public static void main (String[]args){
        int[] myArray = {1,8,3,0,2};


        for(int i=0; i<myArray.length-1; i++){
        if(myArray[i]<myArray[i+1]){

        }
        else{
            int temp=myArray[i];
            myArray[i]=myArray[i+1];
            myArray[i+1]=temp;
        }

        System.out.println(Arrays.toString(myArray));
        }   
    }
}

Output: [1, 3, 0, 2, 8]

所以我们首先检查数组中的第一个值是否小于下一个值。如果是，那么不要做任何事情。如果不是，则交换两者。

这种排序算法的问题在于它不会将第一个值与第三个值交换，或者第二个值与第五个值交换，等等。

我意识到如果我们添加第二个 for 循环来重复我的代码中的 for 循环，这种排序就可以完美地工作：

for(int n=myArray.length; n>1; n=n-1){
...
}

我也意识到这种排序叫做冒泡排序，但是请解释一下这个for循环的重要作用，我很遗憾我完全不明白它的作用？ : /

Answer 1

假设这个算法的最坏情况，一个数组倒序排列，看看一个循环会发生什么

4 3 2 1 0    original array
3 4 2 1 0    after one swap
3 2 4 1 0    after two swaps
3 2 1 4 0    after three swaps
3 2 1 0 4    after the complete loop

你看到现在只有最大的元素在正确的位置，其余的仍然是倒序的。第二次通过后，第二大元素也会位于正确的位置，依此类推。

请注意，第一次之后的遍历不必遍历整个数组（但这不会造成伤害），因为越来越多的元素已经到达了它们的最终位置。

Answer 2

老实说，我对你的问题有点困惑。通常我建议添加诊断打印输出，但您已经有一个。如您所见，只进行一次传递最多可以将一个项目与其旁边的一个交换。您无法以这种方式对数组进行完全排序，因为一旦您处理了 [i] 处的一个元素，您的算法当然不能将该元素移动到其他任何地方。因此，如果它在一次通过后不在最终的正确位置，它就永远不会到达那里。 特别是，给定的元素每次只能移动到左边最多1个位置。最坏的情况是如果输入是在进入之前按递减顺序排序。

当您添加一个执行多次传递的外部循环时，它每次都会对数组进行更多排序，直到最终排序。执行 myArray.length - 1 遍保证即使是最坏情况的元素也有机会 "moved" 通过整个数组到达正确的位置，因为在最坏的情况下输入它保证你能够移动一个元素 left 穿过整个数组（在长度为 n 的数组中需要 n-1 移动将最后一个位置的元素放到第一个位置——如果没有点击，将其画在纸上并数数）。

我的意思是，您的工具集中缺少一项您真正应该学习的重要技能，那就是您需要习惯于可视化代码的作用。有几种方法可以做到这一点：

Research the algorithm you are implementing. The linked wiki article on bubble sort pretty clearly explains the algorithm in the step-by-step section.
有了一些经验，您的头脑就会明白。
在纸上解决问题。
在调试器中逐行跟踪。
为您的程序添加临时跟踪打印输出。
当然，有时会通过破坏算法并观察变化来试验算法。

你选择了#5 和#6，你只需要学习如何解读这些信息。 Here is a working version of your sort，例如（忽略其他潜在的代码改进，我确信这里的其他答案会帮助你沿着这些路线）添加一个额外的打印来分隔输出中的通道：

public static void main (String[]args){
    int[] myArray = {1,8,3,0,2};

    for(int n=myArray.length; n>1; n=n-1){
        System.out.println("Outer loop: " + n);
        for(int i=0; i<myArray.length-1; i++){
            if(myArray[i]<myArray[i+1]){
            }
            else{
                int temp=myArray[i];
                myArray[i]=myArray[i+1];
                myArray[i+1]=temp;
            }
            System.out.println(Arrays.toString(myArray));
        }   
    }
}

这输出：

Outer loop: 5
[1, 8, 3, 0, 2]
[1, 3, 8, 0, 2]
[1, 3, 0, 8, 2]
[1, 3, 0, 2, 8]
Outer loop: 4
[1, 3, 0, 2, 8]
[1, 0, 3, 2, 8]
[1, 0, 2, 3, 8]
[1, 0, 2, 3, 8]
Outer loop: 3
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
Outer loop: 2
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]
[0, 1, 2, 3, 8]

如您所见，在第一次通过后它没有完全排序。第二关更近一些。在这种情况下，第三遍完成了它。在这种情况下，是 0 阻碍了一切：0 必须向左移动 3 个位置，因此您必须至少完成 3 次传递。

要获得更清晰的图像，请尝试输入最坏情况 [8, 3, 2, 1, 0] 的 ideone 示例。

Answer 3

除了添加第二个循环你还可以说

boolean change = true;
while (change) {
   change = false;
   ...
     if (a[i] > a[i + 1]) { // write it like this and you don't need an else
       change = true;
       // swap
     }
   ...
}

两者都有效，因为对数组进行排序所需的最大遍数为 n - 1。在最坏的情况下，数组按降序而不是升序排序，元素将像水泡一样游荡到最后面。在第一次迭代中，第一个元素将在最后一个位置结束，在第二次迭代中，最初的第二个元素（现在是第一个）将移动到倒数第二个位置，依此类推。所以你可以看到你只需要 n-1 次迭代，因为在第 (n-1) 次迭代中，最初的倒数第二个元素（现在是第一个）将在第二个位置结束，而最初的最后一个元素（现在是第一个）是已经正确排序。

您还可以注意到，在每次迭代中（至少）数组末尾的另一个元素最终位于其正确位置，因此您可以在每次迭代中减少内部循环的最大值。

创建了几乎可以工作的排序算法，但我不明白第二个 for 循环

Created almost working sort algorithm but I don't understand the second for-loop

java

sorting

algorithm

bubble-sort