冒泡排序Java不同的输出

Question

我一直在面对一个非常令人困惑的情况，我写了这个BubbleSort程序，它运行得很好。正确输出:

public class BubbleSortInput {
private static void Sorting(int[] intArray)
{
    int i, temp=0;
    int n = intArray.length;
    for(i=0; i < n - 1; i++)
    {
        for(int j = 0; j < n-i-1; j++)
        {
            if(intArray[i]>intArray[i+1])
            {
                temp = intArray[i+1];
                intArray[i] = intArray[i+1];
                intArray[i] = temp;
            }
        }
    }
}
public static void main(String[] args) {
    int array[] = {1,5,65,34,76,234};
    Sorting(array);
    for(int k = 0; k < array.length; k++)
    {
        System.out.println(array[k]);
    }
}
}

然而，我尝试在另一个类的main方法中编写基本相同的代码:

class BubbleSort {
public static void main(String[] args) {
   int numbers[] = {12,43,65,12,65,92,32,54};
   int i,temp=0;
    for(i=0; i < numbers.length-1; i++)
    {
        for(int j = 0; j < numbers.length-i-1; j++)
        {
            if(numbers[i]>numbers[i+1])
            {
                temp = numbers[i+1];
                numbers[i] = numbers[i+1];
                numbers[i]= temp;
            }
        }
    }
    for(i=0;i<numbers.length;i++)
    {
        System.out.println(numbers[i]);
    }
}
}

我在第二个文件上得到的输出是完全错误的，即使我使用了几乎相同的代码，有人能解释一下吗?

Output: 
12
43
12
12
65
32
32
54

Answer 1

正如其他人指出的那样，您应该看看冒泡排序算法。提醒一下，在声明您的原始代码运行良好之前，请运行许多测试用例。为了清楚起见，第一个程序也给出了错误的输出。你得到的输入集合的输出可能是真的，但是开始的时候排序有点乱。在第一个代码中尝试使用第二个程序中使用的输入集，并找出错误。另外，看看for循环中的交换代码。

                temp = intArray[i+1];
                intArray[i] = intArray[i+1];
                intArray[i] = temp;

您将位置[i+1]的值赋给temp，并且您再次将位置[i+1]的值赋给位置i，因此位置[i]的值在此过程中丢失了。现在位置[i]和[i+1]的值是相同的。所以也要努力。

这一边。在冒泡排序中，排序是通过交换相邻的元素来完成的。因此，在第一次传递结束时(升序排序)，数组中最大的元素将位于末尾。此过程将一直进行，直到所有元素都排序完毕。

Example:
First Pass:
( 6 1 3 2 9 ) –> ( 1 6 3 2 9 ), Here, algorithm compares the first two elements, and swaps since 6 > 1.
( 1 6 3 2 9 ) –>  ( 1 3 6 2 9 ), Swap since 6 > 3
( 1 3 6 2 9 ) –>  ( 1 3 2 6 9 ), Swap since 6 > 2
( 1 3 2 6 9 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (9 > 6), algorithm does not swap them.
Second Pass:
( 1 3 2 6 9 ) –> ( 1 3 2 6 9 )
( 1 3 2 6 9 ) –> ( 1 3 4 6 9 ), Swap since 3 > 2
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )
( 1 2 3 5 9) –>  (1 2 3 5 9 )
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.
Third Pass:
( 1 2 3 5 9 ) –> (1 2 3 5 9 )
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )
( 1 2 3 5 9 ) –> ( 1 2 3 5 9 )

Answer 2

我不认为你的气泡排序代码是正确的。这是你的循环:

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

注意，永远不要使用变量j。它所做的就是循环遍历数组，如果第一个元素比第二个元素大，然后交换两个元素。您应该再次查看Bubble排序算法并重新编写代码。

Answer 3

您使用的排序逻辑不正确。

冒泡排序比较每一对相邻的项，如果它们的顺序错误(不是升序)，则交换它们。在第一次传递结束时(升序排序)，数组中最大的元素将位于最后一个索引处。在第二次遍历结束时(升序排序)，数组中的第二大元素将位于倒数第二个索引处，依此类推.....

请访问http://visualgo.net/sorting以获得更好的理解。

所以，在你的代码中，你应该比较第二次初始化的项目(在你的例子中是变量j)。修改后应该是这样的:

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