冒泡排序
冒泡排序比较相邻元素，交换顺序错误的一对。每轮从左向右扫描，把未排序部分的最大值送到末尾。它是稳定的比较排序，平均和最坏时间复杂度为 O(n²)，额外空间为 O(1)。加入提前结束检查后，最好时间复杂度为 O(n)。
把数组看成一排只能交换邻居的数。大数可以沿一轮扫描走到右端，小数每轮却只能向左移动一格。默认输入把最小值 7 放在最右端，它要经过 n - 1 轮才能到达开头。
冒泡排序如何工作
外层循环的 i 从 0 到 n - 2，记录轮次。内层循环的 j 从 0 到 n - 2 - i，比较 arr[j] 和 arr[j + 1]。左值大于右值时交换。
处理完位置 j 的比较后，arr[j + 1] 是 arr[0..j + 1] 中的最大值。动画的 max 标记跟随这个最大值：发生交换时，标记随左值移到右边；不交换时，右值接过标记。最后一次比较结束后，未排序部分的最大值到达最终位置。
因此，第 i 轮结束后，最后 i + 1 个位置存放最大的 i + 1 个值，顺序和位置都已确定。下一轮少比较一对。画布上的分隔线标出未排序部分与绿色有序后缀的边界。
课程提供两个版本。经典版（Classic）总是执行 n - 1 轮。优化版（Optimized）在每轮开始时把 swapped 设为 false，发生交换时设为 true。如果整轮没有交换，说明所有相邻元素都有序，可以结束。两个版本的比较和交换规则相同，区别是优化版可以跳过剩余轮次。
冒泡排序逐步演示
默认使用经典版，输入为 [24, 38, 12, 45, 19, 31, 7]。7 位于下标 6，每轮只能向左移动一次，所以需要六轮才能到达下标 0。
第 1 轮比较六次。24 ≤ 38，不交换，38 成为当前最大值。38 > 12，交换。38 ≤ 45，最大值变成 45。随后 45 依次与 19、31、7 交换。本轮共交换四次，数组变为 [24, 12, 38, 19, 31, 7, 45]。45 在下标 6 就位，7 移到下标 5。
第 2 轮比较五次。24 > 12，交换；24 ≤ 38，不交换；随后 38 依次与 19、31、7 交换。数组变为 [12, 24, 19, 31, 7, 38, 45]。38 在下标 5 就位，有序后缀为 [38, 45]。
第 3 至第 6 轮依次确定 31、24、19、12 的位置。7 从下标 4 移到 3、2、1，最后到 0。结果为 [7, 12, 19, 24, 31, 38, 45]，共六轮、21 次比较、13 次交换。
切换到优化版，课程载入 [30, 12, 23, 47, 58, 76, 91]。第 1 轮把 30 与 12、23 交换，得到 [12, 23, 30, 47, 58, 76, 91]。第 2 轮检查剩余五对相邻元素，没有交换，swapped 保持 false。算法结束，共 11 次比较、2 次交换，第 3 至第 6 轮不执行。
动画中的 j 和 j + 1 指向当前比较的一对，max 跟随已扫描部分的最大值。经典版每轮结束后，有序后缀增加一格。优化版若整轮没有交换，整行变绿并结束。
时间与空间复杂度
| 情况 | 经典版 | 优化版 |
|---|---|---|
| 最好：输入已有序 | O(n²) | O(n) |
| 平均 | O(n²) | O(n²) |
| 最坏：输入逆序 | O(n²) | O(n²) |
比较次数和交换次数要分开计算。经典版第一轮比较 n - 1 次，第二轮比较 n - 2 次，直到最后一轮比较一次：
(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2
七个元素需要 6 + 5 + 4 + 3 + 2 + 1 = 21 次比较。初始顺序不影响这个总数，只影响交换次数。
优化版在整轮结束后检查 swapped。对于已有序的数组，第一轮比较 n - 1 次，没有交换，时间复杂度为 O(n)。对于课程的优化版输入，第一轮完成两次交换，第二轮确认有序，总计 11 次比较。
逆序输入中，每次比较都会交换。七个元素让两个版本都执行 21 次比较和 21 次交换，所以优化版的最坏时间复杂度仍是 O(n²)。
两个版本都不创建另一个数组，交换所用的临时变量占 O(1) 空间。严格的 > 条件保证稳定性：相等元素不会交换。改成 >= 会破坏这一性质。
边界情况
- 一个元素：预设
[42]没有相邻元素对，初始化后就结束，不进入任何一轮。 - 已有序：
[12, 23, 30, 47, 58, 76, 91]是优化版的最好情况，六次比较，零次交换。 - 接近有序：
[12, 23, 30, 47, 58, 91, 76]在第一轮交换一次。第二轮没有交换，优化版在 11 次比较后结束。 - 逆序：经典版处理
[91, 76, 58, 47, 30, 23, 12]时，21 次比较全部触发交换。 - 所有值相等：五个
42不会交换。优化版比较四次后结束，相等元素保持原顺序。
常见错误
已有序输入可以检查提前结束，逆序输入可以检查每次交换，相等输入可以检查稳定性。
- 内层循环边界写错：代码使用
j < n - 1 - i，最后一次比较从j = n - 2 - i开始。多走一步，第一轮会越界，后续轮次会进入有序后缀；少走一步，最大值可能没有到达末尾。 - 重置和检查
swapped的时机写错：每轮开始前重置，整轮结束后检查。只在外层循环之前重置，后续轮次就无法消除早先的交换记录；在内层循环中检查，会把一对元素有序误当成整个数组有序。 - 覆盖交换前的值：语言不支持元组赋值时，先保存左值，再覆盖单元。比较条件保持
>，相等元素才不会越过彼此。 - 把优化版写成 O(n)：O(n) 只描述最好情况。平均和最坏时间复杂度仍为 O(n²)。