Selection Sort排序方法失效？Java实现排序结果异常求助

Hey there! Let's dig into why your selection sort isn't producing the expected output. From the mismatch between your desired and actual results, it looks like the logic for either finding the maximum element or swapping it into the correct position is off. Let's break down the most likely issues and fix them.

Common Issues & Fixes #

1. Your findMax method isn't searching the correct unsorted range

Selection sort works by repeatedly narrowing down the unsorted portion of the array. When you swap the maximum element to the end of the unsorted range, the next search for the maximum should exclude the already sorted elements at the end. If you're always searching the entire array, you might end up re-swapping elements that are already in place.

For example, if your process method calls findMax with the full array length every time:

// Wrong: searches the entire array every time
int maxIndex = findMax(arr, 0, arr.length - 1);

You should instead pass the current end of the unsorted range (which decreases each iteration):

// Correct: searches only the unsorted portion [0, lastUnsortedIndex]
int maxIndex = findMax(arr, 0, lastUnsortedIndex);

2. The comparison logic in findMax is reversed

If your findMax method is actually finding the minimum element by accident (using < instead of >), that would throw off your swaps. Double-check the comparison:

Wrong (finds minimum instead of maximum):

public int findMax(double[] arr, int start, int end) {
    int maxIndex = start;
    for (int j = start + 1; j <= end; j++) {
        if (arr[j] < arr[maxIndex]) { // Reversed comparison
            maxIndex = j;
        }
    }
    return maxIndex;
}

Correct:

public int findMax(double[] arr, int start, int end) {
    int maxIndex = start;
    for (int j = start + 1; j <= end; j++) {
        if (arr[j] > arr[maxIndex]) { // Correctly checks for larger elements
            maxIndex = j;
        }
    }
    return maxIndex;
}

3. Swapping with the wrong index

You mentioned you want to swap the maximum element with the last, then second-last, etc., of the unsorted range. If you're swapping with the start of the range instead of the end, you'll get the jumbled order you're seeing.

Wrong (swaps with start index):

swap(arr, maxIndex, start);

Correct (swaps with end of unsorted range):

swap(arr, maxIndex, lastUnsortedIndex);

Full Working Example #

Here's how the complete corrected code might look:

public class SelectionSort {

    public static int findMax(double[] arr, int start, int end) {
        int maxIndex = start;
        for (int j = start + 1; j <= end; j++) {
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }
        return maxIndex;
    }

    public static void swap(double[] arr, int i, int j) {
        double temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void process(double[] arr) {
        int lastUnsortedIndex = arr.length - 1;
        while (lastUnsortedIndex > 0) {
            int maxIndex = findMax(arr, 0, lastUnsortedIndex);
            swap(arr, maxIndex, lastUnsortedIndex);
            lastUnsortedIndex--;
        }
    }

    public static void main(String[] args) {
        double[] arr = {7.4, 2.0, 8.1, 3.7, 6.2, 8.5, 9.9, 15.7}; // Example input matching your output
        process(arr);
        // Prints [2.0, 3.7, 6.2, 7.4, 8.1, 8.5, 9.9, 15.7]
        System.out.println(java.util.Arrays.toString(arr));
    }
}

Why This Works #

• We start with the entire array as unsorted.
• In each iteration, we find the maximum element in the unsorted portion, swap it to the end of that portion (marking it as sorted), then shrink the unsorted range by one.
• This ensures each element moves directly to its correct position in the final sorted array.

内容的提问来源于stack exchange，提问作者Shuryu Kisuke