Java冒泡排序实现与优化：原理图解及代码示例

什么是冒泡排序

冒泡排序（Bubble Sort）是一种简单的交换排序方法。它的核心理念是将待排序数组中的每个元素想象成水中的气泡，根据数值大小，通过两两交换位置，“一步步移动到队伍的一端”，最终形成有序序列（通常是从大到小或从小到大）。

第1步：理解算法的运行原理

我们可以用一个队列站队的例子来形象化这个过程。假设教官需要让一群队员按从矮到高排队：

1. 比较与交换：从头开始，依次比较相邻的两个队员。如果前一个队员比后一个高，就交换他们的站位；否则保持不变。
2. 推进至末尾：不断向后移动并比较，直到处理完所有相邻元素。经过这一轮，最高的那个队员一定会被“推”到队尾的最终位置上。
3. 重复循环：接着对剩下的未归位部分重复上述操作，次高的队员会被排到倒数第二的位置……

第2步：手动推演排序过程

为了看清细节，我们使用无序数组 [3, 14, 32, 16, 53, 8] 进行升序排列拆解：

第一轮：找出最大值（53）归位

初始值：[3, 14, 32, 16, 53, 8]

经历多次相邻交换后，最大的数字 53 一路被“推”到了最后。
第一轮结束结果：[3, 14, 16, 32, 8, 53]

第二轮：处理剩余部分，找出次大值（32）归位

此时只需比较前5个元素即可，因为 53 已经就位。
初始值：[3, 14, 16, 32, 8, 53] （仅看前5个）

第二轮结束结果：[3, 14, 16, 8, 32, 53]

第三轮：继续缩小范围，找出 16 归位

第二轮结束结果：[3, 14, 16, 8, 32, 53]

第三轮结束结果：[3, 14, 8, 16, 32, 53]

第四轮：继续缩小范围，找出 14 归位

第三轮结束结果：[3, 14, 8, 16, 32, 53]

第四轮结束结果：[3, 8, 14, 16, 32, 53]

第五轮：收尾确认

第四轮结束结果：[3, 8, 14, 16, 32, 53]

第五轮结束后，数组顺序完全正确：[3, 8, 14, 16, 32, 53]，算法至此完成。

第3步：编写基础版 Java 代码

在实现过程中，可以通过内层循环变量控制遍历的范围。以下是直接套用标准逻辑的 Java 实现：

public static void bubbleSort(int[] array){
    // 外层循环控制需要进行几轮比较（长度为 n 的数组需要 n-1 轮）
    for(int i=0; i < array.length-1; i++){
        int num = 0; // 记录本轮比较次数
        // 内层循环负责相邻元素的比对
        for(int j=0; j < array.length-1; j++){
            if(array[j] > array[j+1]){
                // 发现逆序，执行换位操作
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
            num = num + 1;
        }
        // 打印每轮的中间状态
        System.out.print("第"+(i+1)+"轮：[");
        for (int a=0; a<array.length; a++) {
            if(a != array.length-1)
                System.out.print(array[a]+",");
            else
                System.out.print(array[a]+"]");
        }
        System.out.println(",比较了："+num+" 次");
    }
}

第4步：分析性能瓶颈与优化方案

观察上面代码的输出日志可以发现一个问题：

•    第1轮结果：[3,14,16,32,8,53], 每轮比较了：5 次
     第2轮结果：[3,14,16,8,32,53], 每轮比较了：5 次
     ...
     第5轮结果：[3,8,14,16,32,53], 每轮比较了：5 次

对于一个有6个元素的数组，总共进行了 5 × 5 = 25 次左右的实际判断，加上边界开销达到约30次比较。但实际上，随着每轮最大值的排出，后半部分的元素就已经处于有序状态了。

例如在第四轮中，当 14 与 8 换完后，后面的 16, 32, 53 实际上在之前的轮次中已经被确认为正确的相对顺序。因此，如果还去逐个拿它们做比较，纯属徒劳，白白增加了程序运行的压力。

优化策略：在内层循环中加入限制条件。既然第 i 轮会把该轮的最大值放在末尾，那么下一轮只需要比较到 array.length - 1 - i 的位置即可。

第5步：获取优化后的精简代码

修改核心在于 j 的判断条件：

public static void bubbleSortOptimized(int[] array){
    for(int i=0; i < array.length-1; i++){ // 一共 n-1 趟
        int num = 0;
        // 【关键优化】每一轮确定了一位最大值，下次少比较一次
        for(int j=0; j < array.length-1-i; j++){
             // 换位
             int temp = array[j];
             array[j] = array[j+1];
             array[j+1] = temp;
        }
        num = num+1;
        
        // 同样打印结果方便直观对比
        System.out.print("第"+(i+1)+"轮结果：[");
        for (int a=0; a<array.length; a++){
            if(a!=array.length-1)
                System.out.print(array[a]+",");
            else
                System.out.print(array[a]+"]");
        }
        System.out.println(",每轮比较了："+num+" 次");
    }
}

第6步：验证优化效果与理论依据

运行优化版代码后的输出日志如下：

• 第1轮结果：[3,14,16,32,8,53], 每轮比较了：5 次
  第2轮结果：[3,14,16,8,32,53], 每轮比较了：4 次
  第3轮结果：[3,14,8,16,32,53], 每轮比较了：3 次
  第4轮结果：[3,8,14,16,32,53], 每轮比较了：2 次
  第5轮结果：[3,8,14,16,32,53], 每轮比较了：1 次

对比总结：原始数据量下，总比较次数由约 30 次降至 15 次。对于长度为 n 的数组，总的比较次数构成了一个等差数列：

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = 0.5n² - 0.5n

根据时间复杂度的计算规则，只取最高阶项并忽略系数，因此冒泡排序的时间复杂度恒定为 O(n²)。

以上就是关于Java冒泡排序的实现原理、图解步骤以及代码优化的详细内容，更多关于Java常见排序算法实战的资料请关注本站其它相关文章！