使用 Java 编码冒泡排序

Question

我不知道我是否正确地编写了这段代码，但是有人可以确认我的 doBubbleSort 方法及其在 main 方法中的实现是否编写正确吗？我的编码要求我创建一个大小为 20 的数组，并用 1 到 1000 之间的随机整数填充它，而不对它们进行硬编码。结果应该显示原始的、未排序的整数列表；然后在单独的行上显示冒泡排序算法的每一遍。我必须重复该程序，直到用户选择退出。 **我进行了编辑以确保无论我使用什么变量，它都是根据 ArrayLists 声明的。

我希望输出结果的示例如下所示（尽管当我尝试执行 20 时它只显示 5 个整数）：

未排序列表：68 3 298 290 1
通过 1: 3 68 290 1 298
通过 2：3 68 1 290 298
通过 3：3 1 68 290 298
通过 4：1 3 68 290 298

// Used to capture keyboard input
import java.util.*;

// Our class called BubbleSort
public class BubbleSort {

    // Create doBubbleSort method 
    public static void doBubbleSort(ArrayList<Integer> arr) {
        boolean needNextPass = true;
        while (needNextPass) {
            // Array may be sorted and next pass not needed 
            needNextPass = false;
            // Swap list
            for (int i = 0; i < arr.size()-1; i++) {
                if (arr.get(i) > arr.get(i+1)) {
                    int temp = arr.get(i);
                    arr.set(i, arr.get(i+1));
                    arr.set(i+1, temp);
                    printOut(i+1, arr); // using printOut method
                    needNextPass = true; // Next pass still needed
                }
            }
        }
    }

    private static void printOut(int pass, ArrayList<Integer> list) {
        System.out.print("PASS " + pass + ": ");
        for (int i = 0; i < list.size()-1; i++) {
            System.out.print(list.get(i) + ", ");
        }
        // Shows very last integer with a period
        System.out.print(list.get(list.size()-1) + "."); 
        System.out.println();
    }

    // Main method
    public static void main(String[] args) {
        ArrayList<Integer> array = new ArrayList<Integer>(); // Declare and instantiate a new ArrayList object
        Scanner userChoice = new Scanner(System.in); // User input for quitting program
        String choice = ""; // Will hold user choice to quit program
        boolean inputFlag = false; // True if input is valid, false otherwise

        // Repeat program until user chooses to quit
        while (inputFlag = true) {
            System.out.print("\nWould you like to continue the program? (Y/N): ");
            choice = userChoice.nextLine();
            if (choice.equalsIgnoreCase("Y")) {
                try {
                    /* Create an array of size 20 and populate it with random integers between 1 and 1000.
                    Do not ask user for the numbers and do not hard code them */
                    for (int i = 0; i < 20; i++) {
                        int integer = (int)(1000.0 * Math.random());
                        array.add(integer);
                    }
                    System.out.print("\nUNSORTED LIST: ");

                    //Display the 20 size of the unsorted ArrayList 
                    for (int i = 0; i < array.size() - 1; i++) {
                        System.out.print(array.get(i) + ", ");
                    }
                    // Shows very last integer with a period
                    System.out.print(array.get(array.size() - 1) + "."); 
                    System.out.println();
                    doBubbleSort(array);
                }

                catch (IndexOutOfBoundsException e) {
                    System.out.println("\nThere is an out of bounds error in the ArrayList.");
                }
            }
            else if (choice.equalsIgnoreCase("N")) {
                break;
            }
            // Error message when inputting anything other than Y/N
            else { 
                System.out.println("\nERROR. Only Y, y, N, or n may be inputted.");
                System.out.println("Please try again.");
            }
        }
    }
}

Answer 1

您为冒泡排序编写了太多样板代码。对于冒泡排序，使用递归方法。我为你写了简单的冒泡方法，用输出做你想做的事

private int[] bubbleSort(int[] arr){

    int c;
    boolean isArranged = false;

    for (int i = 0; i < arr.length; i++) {
        if (i < (arr.length - 1) && arr[i] > arr[i+1]){
            c = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = c;
            isArranged = true;
        }
    }

    if (isArranged){
        return bubbleSort(arr);
    }else{
        return arr;
    }
}

这样称呼：

Scanner in = new Scanner(System.in);
    int length = in.nextInt();
    int[] arr = new int[length];

    for (int i = 0; i < length; i++) {
        arr[i] = in.nextInt();
    }

    Main main = new Main();

    int[] newArr = main.bubbleSort(arr);

    for (int i = 0; i < newArr.length; i++) {
        System.out.print(newArr[i] + " ");
    }

您可以编写 ArrayList 而不是 int 数组。

Answer 2

随着您的实施，由于您似乎是新学习的，因此您应该更改一些内容。首先，由于您在 doBubbleSort 方法中使用了一个 int 数组，因此在 main 方法中也使用一个 int 数组。

冒泡排序的实现也需要更改。您应该首先仔细研究其逻辑。没有必要每次都遍历整个数组。

// Create doBubbleSort method 
public static void doBubbleSort(int[] arr) {
    boolean needNextPass = true;
    // Array may be sorted and next pass not needed 
    // Swap list
    for (int i = 0; i < arr.length - 1; i++) {
        if (needNextPass) {
            needNextPass = false;
            for (int j = arr.length - 1; j > i; j--) {
                int temp;
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    needNextPass = true; // Next pass still needed
                }
            }
            printOut(i + 1, arr); // using printOut method
        }
    }
}

然后，打印数组。

private static void printOut(int pass, int[] list) {
    System.out.print("PASS " + pass + ": ");
    for (int i = 0; i < list.length - 1; i++) {
        System.out.print(list[i] + ", ");
    }
    // Shows very last integer with a period
    System.out.print(list[list.length - 1] + ".");
    System.out.println();
}

现在是主要方法。我已经更改了重新运行程序的输入处理部分，并使用了您最初发布的 int 数组。

// Main method
public static void main(String[] args) {
    int[] array = new int[20]; // Declare and instantiate a new ArrayList object
    Scanner userChoice = new Scanner(System.in); // User input for quitting program
    boolean inputFlag = true; // True if input is valid, false otherwise
    String choice;

    // Repeat program until user chooses to quit
    while (inputFlag == true) {

        try {
            /* Create an array of size 20 and populate it with random integers between 1 and 1000.
             Do not ask user for the numbers and do not hard code them */
            for (int i = 0; i < 20; i++) {
                int integer = (int) (1000.0 * Math.random());
                array[i] = integer;
            }
            System.out.print("\nUNSORTED LIST: ");

            //Display the 20 size of the unsorted ArrayList 
            for (int i = 0; i < array.length - 1; i++) {
                System.out.print(array[i] + ", ");
            }
            // Shows very last integer with a period
            System.out.print(array[array.length - 1] + ".");
            System.out.println();
            doBubbleSort(array);
        } catch (IndexOutOfBoundsException e) {
            System.out.println("\nThere is an out of bounds error in the ArrayList.");
        }

        System.out.print("\nWould you like to continue the program? (Y/N): ");
        choice = userChoice.nextLine();

        while (!(choice.equalsIgnoreCase("Y")) && !(choice.equalsIgnoreCase("N"))) {
            // Error message when inputting anything other than Y/N
            System.out.println("\nERROR. Only Y, y, N, or n may be inputted.");
            System.out.println("Please try again.");
            choice = userChoice.nextLine();
        }

        if (choice.equalsIgnoreCase("N")) {
            inputFlag = false;
        }

    }
}

}

使用 Java 编码冒泡排序

Coding Bubble Sort using Java

java

sorting

bubble-sort