使用 ArrayList 进行选择排序

Question

我正在尝试使用 ArrayList 编写选择排序代码。我的程序要求我创建一个大小为 20 的数组，并用 1 到 1000 之间的随机整数填充它（无用户输入或硬代码）。输出将需要显示原始未排序的整数列表，并在单独的行上显示排序算法的每一次通过。

我尝试为选择排序创建一个方法，但我遇到了困难，因为我不确定如何将代码实现到我的主要方法中。

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

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

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

// Our class called SelectionSort
public class SelectionSort {

// Create doSelectionSort method 
public static int[] doSelectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int pos = i;
        // find position of smallest num between (i + 1)th element and last element
        for (int j = i + 1; j <= arr.length; j++) {
            if (arr[j] < arr[pos])
                pos = j;

            // Swap min (smallest num) to current position on array
            int min = arr[pos];
            arr[pos] = arr[i];
            arr[i] = min;
        }
    }
    return arr;
}

// 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();
            }

            catch (IndexOutOfBoundsException e) {
                System.out.println("\nThere is an out of bounds error in the ArrayList.");
            }
            // Display each pass of the sorting algorithm on a separate line
            for (int i = 1; i < array.size(); i++) {
                System.out.print("PASS " + i + ": ");
                for (int arr2:array) {
                    System.out.print(arr2 + ", ");
                }
                System.out.print(array.get(array.size() - 1) + ".\n");
            }
        array.clear();
        }
        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

您的方法 doSelectionSort 似乎没问题，但它完成了整个排序。如果你想显示每次迭代你只需要添加一行：

public static int[] doSelectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int pos = i;
        // find position of smallest num between (i + 1)th element and last element
        for (int j = i + 1; j <= arr.length; j++) {
            if (arr[j] < arr[pos])
                pos = j;

            // Swap min (smallest num) to current position on array
            int min = arr[pos];
            arr[pos] = arr[i];
            arr[i] = min;
        }
        System.out.println("Pass "+pos+" : "+arr);
    }
    return arr;
}

Answer 2

我修改了你的代码，现在应该可以了。

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

// Our class called SelectionSort
public class SelectionSort {

    // Create doSelectionSort method 
    public static void doSelectionSort(ArrayList<Integer> arr) {
        for (int i = 0; i < arr.size(); i++) {
            // find position of smallest num between (i + 1)th element and last element
            int pos = i;
            for (int j = i; j < arr.size(); j++) {
                if (arr.get(j) < arr.get(pos))
                    pos = j;
            }
            // Swap min (smallest num) to current position on array
            int min = arr.get(pos);
            arr.set(pos, arr.get(i));
            arr.set(i, min);
            printOut(i + 1, arr);
        }
    }

    private static void printOut(int pass, ArrayList<Integer> array) {
        System.out.print("PASS " + pass + ": ");
        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();
    }

    // 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();
                    doSelectionSort(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.");
            }
        }
    }
}

使用 ArrayList 进行选择排序

Selection Sort using ArrayList

java

arrays

sorting

arraylist

selection