为什么我的冒泡排序在按升序排序数据时给出错误的输出？

Question

我在 Java 中创建了冒泡排序算法的实现。代码运行良好并给出了有效的输出，但是，由于某种原因，当我按升序对数据进行排序时，它正确地进行了排序，但是当我尝试打印出该语句时遇到了问题。下面是我的代码，以及对问题的稍微更好的描述！

import java.util.Arrays;
import java.util.Scanner;
//import java.util.regex.Pattern;
//import java.util.stream.Stream;
public class BubbleSortNumeric {
    public static void main (String [] args) {
        Integer [] unsortedData = getDataInput();
        Integer [] sortedDataAscending;
        Integer [] sortedDataDescending;
        long start = System.nanoTime();
        sortedDataAscending = bubbleSortAscending(unsortedData);
        sortedDataDescending = bubbleSortDescending(unsortedData);
        long stop = System.nanoTime();
        System.out.println("Ascending: " + Arrays.toString(sortedDataAscending));
        System.out.println("Descening: " + Arrays.toString(sortedDataDescending));
        System.out.println("Execution time: " + ((stop - start) / 1e+6) + "ms.");
    }
    
    private static Integer [] getDataInput() {
        System.out.println("Enter a set of integers seperated by a space.");
        Integer [] userInput = {};
        String strInput;
        try(Scanner sc = new Scanner(System.in)) {
            strInput = sc.nextLine();
        }
        String [] inputData = strInput.split("\s+");
        try {
            userInput = Arrays.asList(inputData).stream().map(Integer::valueOf).toArray(Integer[]::new); 
        }catch(NumberFormatException e) {
            System.out.println("ERROR. Invalid input.\n" + e.getMessage());
        }
       return userInput;
    }
    
    private static Integer [] bubbleSortAscending(Integer[] ascendingUnsorted) {
        int n = ascendingUnsorted.length;
        System.out.println(n);
        if(n == 1) {
            return ascendingUnsorted;
        }
        boolean swapped;
        int temp;
        do {
            swapped = false;
            for(int i = 1; i < n; i++) {
                if(ascendingUnsorted[i - 1] > ascendingUnsorted[i]) {
                    temp = ascendingUnsorted[i - 1];
                    ascendingUnsorted[i - 1] = ascendingUnsorted[i];
                    ascendingUnsorted[i] = temp;
                    swapped = true; 
                }
            }
            n--;
        }while(swapped == true);
        return ascendingUnsorted;
    }
    
    private static Integer [] bubbleSortDescending(Integer [] descendingUnsorted) {
        int n = descendingUnsorted.length;
        if(n == 1) {
            return descendingUnsorted;
        }
        boolean swapped;
        int temp;
        do {
            swapped = false;
            for(int i = 1; i < n; i++) {
                if(descendingUnsorted[i - 1] < descendingUnsorted[i]) {
                    temp = descendingUnsorted[i];
                    descendingUnsorted[i] = descendingUnsorted[i - 1];
                    descendingUnsorted[i - 1] = temp;
                    swapped = true;
                }
            }
            n--;
        }while(swapped == true);
        return descendingUnsorted;
    }
}

当我调用 bubbleSortAscending 时它工作正常，并按升序对数据进行排序。因为我是在计时程序的执行时间，不想把结果打印出来再把数据降序排列。

我的问题是，虽然这两种方法都可以正常工作，但我在打印结果时遇到了问题。发生的情况的示例如下：

输入

1 3 9 2 40 193

输出：

Ascending: [193, 40, 9, 3, 2, 1]

Descening: [193, 40, 9, 3, 2, 1]

Execution time: 0.527142ms.

如果我将 print 语句移动到 sortedDataAscending = bubbleSortAscending(unsortedData); 行之后，那么它会给出正确的输出，但是，正如我已经说过的，我不希望那样。

所以我的问题是，即使我将结果分配给两个不同的变量，为什么当我打印两个变量的答案时，输出是否相同？

Answer 1

我给你一个提示：交换这两行，执行，你会看到魔法。从此

    sortedDataAscending = bubbleSortAscending(unsortedData);
    sortedDataDescending = bubbleSortDescending(unsortedData);

至此

    sortedDataDescending = bubbleSortDescending(unsortedData);
    sortedDataAscending = bubbleSortAscending(unsortedData);

这对您有何启示？

.

您正在修改同一个数组两次！您的所有参考资料

unsortedData
sortedDataAscending
sortedDataDescending

都指向同一个对象：一个数组，先是未排序，然后是升序排序，最后是降序排序。

此时您决定将其打印出来。

两次。

Answer 2

您必须复制输入数组，因为在 Java 您将值作为参考而不是副本传递：

public class BubbleSortNumeric {
    public static void main (String [] args) {
        Integer [] unsortedData1 = getDataInput();
        Integer [] unsortedData2 = new Integer[unsortedData1.length];
        System.arraycopy(unsortedData1, 0, unsortedData2, 0, unsortedData1.length);
        Integer [] sortedDataAscending;
        Integer [] sortedDataDescending;
        long start = System.nanoTime();
        sortedDataAscending = bubbleSortAscending(unsortedData1);
        sortedDataDescending = bubbleSortDescending(unsortedData2);
        // ...

经过测试，您的算法运行良好，只有数组错误：

$ javac BubbleSortNumeric.java  && java BubbleSortNumeric 
Enter a set of integers seperated by a space.
1 3 9 2 40 193

6
Ascending: [1, 2, 3, 9, 40, 193]
Descening: [193, 40, 9, 3, 2, 1]
Execution time: 0.068779ms.

为什么我的冒泡排序在按升序排序数据时给出错误的输出？

Why is my bubble sort giving an incorrect output when sorting data in ascending order?

java

arrays

sorting

bubble-sort