冒泡排序Java不同的输出

Question

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]);
    }
}
}

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 )