java - 带 while 语句的场景

Question

好吧，我正在努力理解冒泡排序算法，这段代码可以工作，但我不明白 while 语句？括号里没有条件，我不知道为什么它继续运行，为什么停止。

public class BubbleSort {
int temp;
boolean flag;
int[] bubbleSort(int[] bs)
{  
    flag=true;//What? 
    while(flag)//Whats happening here? Whats the condition
    {
    flag=false;//Wouldnt that quit the while loop?
    for(int i=0;i<bs.length-1;i++)
    {   
        if(bs[i]>bs[(i+1)])
        {
            temp=bs[i];
            bs[i]=bs[i+1];
            bs[i+1]=temp;
            flag=true;//What does this signify?
        }

    }
}
    return bs;
}

public static void main(String[] args)
{
    BubbleSort thisone = new BubbleSort();
    int[] bacon = {1,0,3,2,4,5};
    int[] potato = thisone.bubbleSort(bacon);
    for(int i=0;i<potato.length;i++)
    {
        System.out.println(potato[i]);
    }

}

}

Answer 1

用伪代码可能更容易理解，而不需要所有特定于语言的东西:

didSwap = true                          # force loop entry
while didSwap:                          # keep going until sorted
    didSwap = false                     # mark sorted
    for each element except last:
        if element > next element:
            swap element, next element
            didSwap = true              # swapped, mark possibly unsorted

didSwap ^(a) 变量最初设置为 true 以确保进入循环。

进入循环后，它会立即设置为 false，这样，无论什么情况下都不会将其设置回 true，循环将在本次迭代后退出。这意味着循环迭代的默认行为是完成，然后退出循环(这里和下面所有关于迭代的讨论都指的是外循环，即while循环，而不是每个的内部)。

现在看看是什么让它恢复为 true。这是本次迭代中任何项目的交换。当发生这种情况时，您知道您至少需要再进行一次循环迭代，因为您可能打乱了在此迭代中先前已完成的项目的顺序。

考虑以下数字的情况，您已完成第一次迭代(尚未完成交换):

5 10 15 7 20
     ^^

从左向右跑，您已经到达15并且您知道前三个数字已经按顺序排列。但随后您到达 7 并将其与 15 交换以修复这两个的顺序。现在你有:

5 10 7 15 20
       ^^

您可以看到，由于您在处理时之前对顺序进行了更改，因此可能会打乱顺序(事实上您已经> 在本例中)，因此您至少需要再通过一次来检查和/或修复该问题。

底线，由于处理列表的顺序性质(从左到右)，只有当到达迭代结束并且在该迭代期间没有执行交换时，您才能确定它已排序。

这就是使用 flag 方法的原因。更简单的实现只是对大小为 n 的列表执行 n * n 迭代之类的操作。这也保证了项目将在最后进行排序，但不会为您提供 flag 方法的早期退出可能性。如果您给它一个已经排序的包含一千个元素的列表，您可以立即看到问题。

天真的方法将处理整个列表一千次，而 flag 方法仅处理一次。

<小时/>

^(a) 我自己更喜欢 didSwap，因为它的用途和意图更清晰。