冒泡排序的原理是什么？如何优化？

简化版

冒泡排序反复比较相邻两个元素，逆序就交换，每一轮都把当前最大的元素「冒泡」到末尾。n 个元素做 n-1 轮。时间平均和最坏都是 O(n²)、空间 O(1)、稳定。优化：如果某一轮没有发生任何交换，说明已经有序，可以提前退出——这样对近乎有序的数组能达到最好 O(n)。

详细版

void bubbleSort(int[] a) {
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {        // 共 n-1 轮
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) { // 每轮把最大的冒到末尾
            if (a[j] > a[j + 1]) {            // 相邻逆序就交换
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;                  // 优化：一轮无交换 → 已有序，提前结束
    }
}

内层 n-1-i：每轮末尾会多固定一个已排好的最大值，下一轮不用再比它。
swapped 标志：一轮没交换说明整体已有序，直接退出。
稳定：只有「严格大于」才交换，相等不交换，相对顺序不变。

完整版教学

一、名字的由来：像气泡上浮

冒泡排序的名字很形象：每一轮从头到尾扫，把相邻的逆序对交换，较大的元素就像气泡一样一步步「浮」到数组末尾。第一轮结束，最大的到了最后一位；第二轮结束，第二大的到了倒数第二位……n-1 轮之后全部就位。理解它先抓住这个画面：每一轮确定一个「当前最大值」的最终位置。

二、逐步走一遍

初始: [5, 3, 8, 4, 2]
第1轮（把最大的 8 冒到末尾）:
  5,3 逆序→ [3,5,8,4,2]
  5,8 顺序，不动
  8,4 逆序→ [3,5,4,8,2]
  8,2 逆序→ [3,5,4,2,8]   ← 8 就位
第2轮: [3,4,2,5,8]（5 就位）
第3轮: [3,2,4,5,8]（4 就位）
第4轮: [2,3,4,5,8]（完成）

每轮内层循环范围逐渐缩小（末尾已排好的不再参与）。

三、两个关键优化

提前退出（swapped 标志）：如果某一轮一次交换都没发生，说明数组已经完全有序，后面的轮次纯属浪费，直接 break。有了这个优化，对已经有序的数组只需一轮扫描 O(n)，这就是冒泡「最好 O(n)」的来源。没有这个优化，冒泡最好也是 O(n²)。
记录最后交换位置：更进一步，可以记录「本轮最后一次交换的位置」，它之后的部分已经有序，下一轮内层循环到这里就行，进一步减少比较。

四、复杂度分析

时间：
- 平均、最坏 O(n²)：需要约 n²/2 次比较和交换（完全逆序时交换最多）。
- 最好 O(n)：数组已有序 + 提前退出优化，只扫一轮。
空间 O(1)：只用常数个临时变量，原地排序。

五、为什么冒泡是稳定的

稳定性指「相等元素排序后相对顺序不变」。冒泡排序只在 a[j] > a[j+1]（严格大于）时才交换，相等的两个元素不会交换，所以它们的先后顺序始终保持。这让冒泡成为稳定排序。

注意：如果把条件写成 a[j] >= a[j+1]（相等也交换），就会破坏稳定性——这是个常见的「手滑」错误。

六、冒泡的定位

冒泡排序时间复杂度高（O(n²)）、交换次数多，实际工程几乎不用——它主要用于教学，帮助理解「相邻交换」「稳定性」「提前退出优化」这些概念。真要排序，快排/归并/库函数远优。但它是排序入门的经典第一课，面试也常拿它考「稳定性」和「优化」。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：每轮结束后，未排序区间的最大值已经移动到右端最终位置。

对应的状态推进是：逐对比较相邻元素，只在左值严格大于右值时交换；无交换可提前结束。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。比较上界 n(n-1)/2；优化后最好 O(n)，平均和最坏 O(n²)。

带数字走一遍：[5,1,4,2,8] 第一轮变为 [1,4,2,5,8]，8 归位。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	适合小规模或近乎有序数据，不适合大规模随机数据
时间复杂度	最好 O(n)，平均/最坏 O(n²)
额外空间	O(1)
关键边界	相等元素不能用 >= 交换，否则破坏稳定性；还要缩短已归位后缀
替代方案	通用库排序通常选快排、归并或 TimSort

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“适合小规模或近乎有序数据，不适合大规模随机数据”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写最好 O(n)，平均/最坏 O(n²) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“比较上界 n(n-1)/2；优化后最好 O(n)，平均和最坏 O(n²)”。
误区：重复值和边界值不会改变代码。 相等元素不能用 >= 交换，否则破坏稳定性；还要缩短已归位后缀。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“每轮结束后，未排序区间的最大值已经移动到右端最终位置”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[5,1,4,2,8] 第一轮变为 [1,4,2,5,8]，8 归位”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“通用库排序通常选快排、归并或 TimSort”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

冒泡排序：反复比较相邻元素、逆序就交换，每轮把最大值冒到末尾，n-1 轮。平均/最坏 O(n²)、空间 O(1)、稳定（只在严格大于时交换，相等不换）。关键优化：一轮无交换就提前退出，让近乎有序时达到最好 O(n)。实际工程不用，主要用于理解相邻交换、稳定性与提前退出优化。

简化版

详细版