Java实现bubblesort冒泡排序无法正确排序所有元素问题排查

问题现象 #

• 基于Java实现冒泡排序时，代码运行后无法得到正确的升序排序结果
• 测试用例输入数组{2,6,7,9,5}，运行后输出为2、5、7、9、6，仅完成少量元素交换，未实现全数组排序

原始问题代码 #

import java.util.Arrays;
public class Arraysort {
    
    static void sort(int[] array) {
        int n = array.length;
        int temp = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < (n-i); j++) {
                if (array[j-1] > array[i]) {
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
    public static void main(String[] args){
        int array[] = {2,6,7,9,5};
        System.out.println("This is my unsorted Array\n");
        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
            System.out.println();
        }
        sort(array);
        System.out.println("This is my sorted Array\n");
        for(int i = 0; i < array.length; i++) {
            System.out.println(array[i] + " ");
        }
    }
}

错误根因 #

冒泡排序的核心规则是内层循环逐次比较相邻位置的两个元素，若前值大于后值则交换，每一轮外层循环会将当前未排序区间的最大值移动到区间末尾。
原代码的核心错误出在内层循环的比较判断条件：

// 错误逻辑：比较对象为j-1位置元素 和 外层循环索引i对应的元素，*并非相邻元素*
if (array[j-1] > array[i])

此处错误将对比的右值写为外层循环索引i对应的元素，而非当前内层遍历到的相邻位置j的元素，导致交换触发条件完全偏离冒泡排序的相邻比较规则，最终只会触发零星的错误交换，无法完成全量排序，和得到的异常输出完全吻合。

修正方案 #

将if判断的对比对象修改为相邻的array[j]即可，同时可以补充两处常规优化：

1. 外层循环最多执行n-1次即可完成全量排序，无需遍历到数组长度n
2. 新增交换标记，若某一轮内层遍历未发生任何交换，说明数组已经完全有序，可提前终止循环减少无效遍历
   修正后的排序方法代码如下：

static void sort(int[] array) {
    int n = array.length;
    int temp = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 1; j < (n - i); j++) {
            // 修正：比较相邻的j-1和j位置元素
            if (array[j-1] > array[j]) {
                temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
                swapped = true;
            }
        }
        // 本轮无交换，数组已有序，直接退出
        if (!swapped) {
            break;
        }
    }
}

替换原sort方法后重新运行，测试数组将得到正确的升序输出：2 5 6 7 9

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