19. 基础排序：冒泡排序 (Bubble Sort)

前置学习：一维数组实战、嵌套循环

现实世界中的数据往往是杂乱无章的，而计算机处理有规律的数据（比如已经按从小到大排好序的数据）速度会快上千百倍。将乱序数据变成有序数据的过程，就叫排序。而在所有的排序算法中，冒泡排序是最经典、最直观的入门必修课。

1. 核心思想：大数下沉，小数上浮

为什么叫“冒泡”？因为它的过程就像水里的气泡一样：比较轻（小）的气泡会往上浮，比较重（大）的石头会往下沉。

规则非常简单，只有一句话： 从头到尾遍历数组，每次比较相邻的两个数字。如果左边的数字大于右边的数字，就交换它们的位置。

2. 图解冒泡过程

假设我们有 4 个数字：[4, 3, 2, 1]。我们希望从小到大排。

第一趟冒泡（找出最大的数扔到最后）：

[4, 3, 2, 1] -> 比较 4 和 3。4 大于 3，交换！ -> [3, 4, 2, 1]
[3, 4, 2, 1] -> 比较 4 和 2。4 大于 2，交换！ -> [3, 2, 4, 1]
[3, 2, 4, 1] -> 比较 4 和 1。4 大于 1，交换！ -> [3, 2, 1, 4] 第一趟结束，最大的 4 像沉入水底一样，已经稳稳地停留在了最后一位。

接下来，只需要对前面剩下的 3 个数字重复这个过程，就可以把 3 沉底... 以此类推。

3. C++ 代码实现

冒泡排序必须使用双重嵌套循环：

外层循环：控制总共要进行几趟冒泡（$N$ 个数字，只需 $N-1$ 趟）。
内层循环：负责在当前趟次里，挨个比较相邻数字并交换。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a[5] = {5, 2, 9, 1, 6};
    int n = 5; // 数组长度
    
    // 外层循环：走 n - 1 趟即可
    for (int i = 0; i < n - 1; i++) {
        
        // ⚠️ 极其重要：内层循环的边界是 n - 1 - i
        for (int j = 0; j < n - 1 - i; j++) {
            
            // 如果前面的数字比后面的大，产生逆序
            if (a[j] > a[j + 1]) {
                // 调用 C++ 内部的神器函数：直接交换两个变量的值
                swap(a[j], a[j + 1]);
            }
            
        }
    }
    
    // 打印排序后的结果
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    // 最终输出：1 2 5 6 9
    return 0;
}

4. 💀 深入理解：内层循环的极限在哪里？

很多同学搞不懂内层循环为什么写成 j < n - 1 - i。这里面藏着两个绝不容犯的错误：

为什么要有 - 1？ 因为循环里面我们要访问 a[j + 1]。如果 j 一路走到 n - 1 的位置，j + 1 就会变成 n，这会导致数组越界 (RE)，直接砸碎别人的柜子！
为什么要有 - i？ 外层循环 i 每走一趟，就说明有 i 个最大的数字已经像石头一样沉到数组末尾了。这些尾部的数字已经排好了序，我们绝对不应该再浪费时间去碰它们。- i 就是为了剔除末尾已经排好的区域。

5. 动手实践

1. 打开左下角的代码沙盒。
2. 上面的代码是“从小到大”排序（升序）。
3. 试着修改代码中 `if` 里面的一个符号，让这组数字变成“从大到小”排序（降序）。
   *(极具挑战：如果你不用 C++ 自带的 `swap` 函数，你能仅借助一个临时的第三方变量 `temp`，手写出交换 `a[j]` 和 `a[j+1]` 的代码吗？)*

19. 基础排序：冒泡排序 (Bubble Sort) ​

1. 核心思想：大数下沉，小数上浮 ​

2. 图解冒泡过程 ​

3. C++ 代码实现 ​

4. 💀 深入理解：内层循环的极限在哪里？ ​