数据结构与算法 / 系统课时

冒泡排序

冒泡排序

冒泡排序通过反复比较相邻元素,把较大的元素逐步交换到数组右端。本课将跟踪每一轮的有序边界,加入提前终止标记,并分析该优化为什么能让已排序输入在线性时间内完成。

学习目标

  • 描述冒泡排序中相邻比较与交换的执行过程。
  • 实现带提前终止优化的 Java 冒泡排序。
  • 判断冒泡排序的复杂度、稳定性和适用限制。

问题定义

给定一个数组,若相邻两个元素满足左侧大于右侧,就交换它们。完整扫描一轮后,本轮遇到的最大元素会移动到未排序区间最右端,因此下一轮无需再次访问这个已经确定的位置。

冒泡排序与提前终止过程

核心原理

第 i 轮结束后,数组末尾至少有 i + 1 个元素已经位于最终位置。于是内层循环的右边界可以写成 n - 1 - i,避免重复比较已确定区间。

冒泡排序的提前终止依赖布尔变量 swapped。每轮开始时将其设为 false;只要发生交换就改为 true。若一轮扫描结束后仍为 false,说明当前数组已经有序,可以立即结束外层循环。

为了保持稳定性,交换条件必须使用严格大于 >。若写成大于等于 >=,两个相等元素也会交换,从而可能改变它们的原始先后顺序。

带提前终止的冒泡排序在数组已经有序时只需完成一轮扫描,最好时间复杂度为 O(n);对互异键的均匀随机排列,平均为 Θ(n²),最坏也为 Θ(n²),额外空间复杂度为 O(1)。

完整可运行示例

下面的程序统计实际执行的轮数、比较次数和交换次数。将代码保存为 BubbleSortDemo.java。

java
import java.util.Arrays;

public class BubbleSortDemo {

    public static void main(String[] args) {
        int[] values = {5, 1, 4, 2, 8};

        SortStats stats = bubbleSort(values);

        System.out.println("排序结果: " + Arrays.toString(values));
        System.out.println("执行轮数: " + stats.passes);
        System.out.println("比较次数: " + stats.comparisons);
        System.out.println("交换次数: " + stats.swaps);
    }

    static SortStats bubbleSort(int[] values) {
        int passes = 0;
        long comparisons = 0;
        long swaps = 0;

        for (int i = 0; i < values.length - 1; i++) {
            boolean swapped = false;
            passes++;

            // 右侧 i 个元素已经位于最终位置,无需再次比较。
            for (int j = 0; j < values.length - 1 - i; j++) {
                comparisons++;
                if (values[j] > values[j + 1]) {
                    int temp = values[j];
                    values[j] = values[j + 1];
                    values[j + 1] = temp;
                    swaps++;
                    swapped = true;
                }
            }

            // 本轮没有交换,说明整个数组已经有序。
            if (!swapped) {
                break;
            }
        }

        return new SortStats(passes, comparisons, swaps);
    }

    static class SortStats {
        final int passes;
        final long comparisons;
        final long swaps;

        SortStats(int passes, long comparisons, long swaps) {
            this.passes = passes;
            this.comparisons = comparisons;
            this.swaps = swaps;
        }
    }
}

运行命令

bash
javac -encoding UTF-8 BubbleSortDemo.java
java BubbleSortDemo

预期输出

text
排序结果: [1, 2, 4, 5, 8]
执行轮数: 3
比较次数: 9
交换次数: 4

优化效果与边界

输入状态 是否提前终止 时间复杂度
已经升序 第一轮后终止 O(n)
基本有序 可能较早终止 取决于逆序分布
逆序 无法提前终止 O(n^2)

提前终止只减少不必要的后续轮次,不会改变逆序输入需要大量相邻交换的事实。每次只交换严格逆序的相邻两项,整个序列的严格逆序对恰好减少一个,所以交换总数等于初始逆序对数。但比较数还与逆序位置有关。比如 [5,1,2,3,4] 和 [2,3,4,5,1] 都有 4 个逆序对。前者执行 2 轮、比较 7 次,后者执行 4 轮、比较 10 次,因为小元素每轮最多向左移动一格。

Tips

  • 每轮开始时必须重新设置 swapped = false,否则旧状态会让提前终止失效。
  • 内层上界使用 values.length - 1 - i,既防止访问 j + 1 越界,也跳过已确定区间。
  • 若只需判断数组是否有序,可复用“一轮无交换”的思想,但不必执行完整排序。

常见错误

1. 忘记缩小右边界

始终扫描到数组末尾不会影响排序正确性,却会重复比较已经确定的元素。应让每轮的比较上界随 i 减小。

2. 使用大于等于作为交换条件

条件 values[j] >= values[j + 1] 会交换相等元素,破坏稳定性。升序冒泡排序应使用 values[j] > values[j + 1]。

本课练习

  1. 用至少两个元素的非递减数组验证一轮、n−1 次比较和零交换。用空数组及单元素验证零轮、零比较。
  2. 扩展统计信息,输出每一轮结束后的数组状态,但不得改变排序结果和提前终止逻辑。

本课总结

  • 冒泡排序通过相邻交换,把当前最大元素逐轮推到未排序区间末端。
  • swapped 标记可让有序输入在 O(n) 时间内结束,但最坏复杂度仍为 O(n^2)。
  • 使用严格大于条件时算法稳定,但频繁交换限制了它在大规模数据上的实用性。

下一课预告

下一课学习归并排序,将任务拆成两个有序子序列再线性合并,并比较所需辅助空间。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

冒泡排序

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通