Java中Bubble Sort（冒泡排序）无法正确排序问题求助

Hey there! That unexpected output [1, 3, 2, 4] from an already sorted array gives us a clear clue there's a small bug in your bubble sort logic—probably tied to loop boundaries, swap conditions, or missing an early exit check. Let's break down the most likely culprits and fix this step by step.

Common Causes for This Exact Behavior #

Let's unpack why an already sorted array would end up with swapped middle elements:

1. Incorrect Inner Loop Boundaries #

If your inner loop doesn't shrink the comparison range as the outer loop progresses, you might re-check (and accidentally swap) elements already in their correct positions. For example, a common mistake is omitting the - i in the inner loop condition:

// Wrong: inner loop doesn't account for sorted tail elements
for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length - 1; j++) { // Missing "- i" here
        if (arr[j] > arr[j+1]) {
            swap(arr, j, j+1);
        }
    }
}

Even with a correct swap condition, this can lead to unnecessary re-scans that might disrupt already sorted segments.

2. Partial Loop Execution #

Your output ([1,3,2,4]) shows the first and last elements stay in place, but the middle pair swaps. This suggests your outer loop is stopping too early (e.g., running only arr.length - 2 times instead of arr.length - 1) or the inner loop is cutting off before reaching the end of the unsorted segment.

3. Reversed or Misplaced Swap Logic #

If you mixed up the swap condition (e.g., using arr[j] < arr[j+1] instead of arr[j] > arr[j+1]) or swapped the wrong indices, you'd trigger unintended swaps even in sorted arrays.

Correct Bubble Sort Implementation (Ascending Order) #

Here's a standard, efficient bubble sort that handles already sorted inputs perfectly, with an early exit to avoid unnecessary work:

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    
    // Outer loop: each pass places the next largest element at the end
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        // Inner loop: only compare the unsorted portion of the array
        for (int j = 0; j < n - 1 - i; j++) {
            // Swap if current element is larger than the next (ascending order)
            if (arr[j] > arr[j + 1]) {
                // Perform swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // Early exit: if no swaps occurred, array is already sorted
        if (!swapped) {
            break;
        }
    }
}

Key Fixes in This Code: #

• Shrinking inner loop: j < n - 1 - i ensures we ignore elements already sorted at the end of the array.
• Early exit flag: The swapped boolean lets us stop sorting immediately once the array is fully ordered—critical for already sorted input, which will exit after the first pass.
• Precise swap condition: arr[j] > arr[j+1] only swaps elements when needed to move larger values toward the end.

How to Verify #

If you replace your code with this implementation, passing [1,2,3,4] will return the exact same array without any swaps. For unsorted inputs like [4,2,1,3], it will correctly sort to [1,2,3,4].

If your original code has a unique bug, feel free to share your exact implementation, and we can pinpoint the exact line causing the issue!

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