冒泡排序：像汽水冒泡一样把数字排好

想象你打开一瓶汽水，无数小气泡从杯底慢慢升上来，越大的气泡升得越快，最后浮到水面。冒泡排序 的工作原理和这个很像：每次比较相邻的两个数字，如果前一个比后一个大，就交换它们的位置。经过一轮又一轮的比较，最大的数字会像气泡一样“浮”到数组的最后面，然后第二大的数浮到倒数第二位……直到所有数字从小到大排好。

下面我们就用这个有趣的方法，把一堆乱糟糟的数字整理得整整齐齐！

冒泡排序是怎么工作的？

假设我们要把数组 [5, 2, 9, 1] 从小到大排序。你可以把每个数字想象成一个同学，他们按照现在的顺序站成一排，我们需要让矮的同学站前面，高的同学站后面。

第一轮：把最高的同学送到队伍末尾

比较第1个（5）和第2个（2），5比2高，交换 → [2, 5, 9, 1]
比较第2个（5）和第3个（9），5比9矮，不交换 → [2, 5, 9, 1]
比较第3个（9）和第4个（1），9比1高，交换 → [2, 5, 1, 9]

第一轮结束后，最高的同学（9）已经到了队伍最后面，他不用再参与下一轮的比较了。

第二轮：把第二高的同学送到倒数第二

比较第1个（2）和第2个（5），2比5矮，不交换 → [2, 5, 1, 9]
比较第2个（5）和第3个（1），5比1高，交换 → [2, 1, 5, 9]

第二轮结束后，第二高的同学（5）到了倒数第二位。注意，最后一位（9）已经排好了，所以这一轮只比较了前三个数字。

第三轮：把第三高的同学送到倒数第三

比较第1个（2）和第2个（1），2比1高，交换 → [1, 2, 5, 9]

第三轮结束后，所有数字都排好了。现在队伍的顺序是 [1, 2, 5, 9]，从矮到高整整齐齐。

为什么要比较 `n-1` 轮？

有 n 个数字，每轮都会把一个最大的数字送到末尾。送完最大的后，剩下的数字有 n-1 个；再送完第二大的，剩下 n-2 个……直到剩下最后一个数字时，它自然就是最小的，不需要再比较了。所以总共需要 n-1 轮。

例如，4个数字需要3轮，5个数字需要4轮。你可以试着自己举一个例子：如果队伍里有5个同学站成一排，最多需要几轮才能按身高排好？答案是4轮。

每轮比较的次数为什么越来越少？

因为每一轮结束后，末尾已经排好的数字就不需要再比较了。所以第1轮比较 n-1 次，第2轮比较 n-2 次……第 i 轮比较 n-i 次。用代码写就是内层循环 j < n - 1 - i。

比如有4个数字：

第1轮（i=0）：比较3次（j从0到2）
第2轮（i=1）：比较2次（j从0到1）
第3轮（i=2）：比较1次（j=0）

这样写既不会重复比较已经排好的数字，也能保证程序运行得快一点。

如何提前结束排序？（聪明的小技巧）

如果在某轮比较中，一次交换都没有发生，说明所有数字已经按顺序排好了，后面的轮次就不用再继续了。这就像你检查队伍：如果从头走到尾，发现每个同学都比前面一个矮（或者相等），那就已经排好了，不用再重复检查。

在代码里，我们可以用一个叫 swapped 的“标记”来记住这一轮有没有交换过。开始时假设没有交换（swapped = false），一旦发生交换，就把标记改成 true。一轮结束后，如果标记仍然是 false，就用 break 跳出外层循环。

这个技巧在数字基本有序时特别有用，比如 [1, 2, 3, 5, 4]，只需要一轮交换就能排好。

用生活中的例子理解冒泡排序

例子1：零花钱排行榜

小明、小红、小刚、小丽的零花钱分别是5元、2元、9元、1元。他们想从少到多排个序。用冒泡排序：

第一轮：5和2比→2在前，5在后；5和9比→不动；9和1比→1在前，9在后 → 结果 [2, 5, 1, 9]
第二轮：2和5比→不动；5和1比→1在前，5在后 → [2, 1, 5, 9]
第三轮：2和1比→1在前，2在后 → [1, 2, 5, 9]

例子2：体育课排队

体育老师让同学们按身高从矮到高排成一排。老师从队伍前面开始，每次比较相邻两个同学的身高，如果前面比后面高，就让他们交换位置。这样走完一轮，最高的同学就到了最后。重复这个过程，直到所有同学都站对位置。

新手容易犯的错误

内层循环的边界写错
常见错误：写成 j < n - 1 或 j < n - i。正确写法是 j < n - 1 - i，因为每轮比较的次数要减去已经排好的 i 个数字。如果写成 j < n - 1，程序依然能运行，但会多比较一些已经排好的数字，浪费了时间。
忘记初始化交换标记
有些人把 swapped 定义在外层循环外面，这样第二轮开始标记还是上一次的 true，会导致提前结束的判断失效。正确做法是每轮开始前都重置为 false。
交换时用了错误的临时变量
交换两个数的经典写法：temp = a; a = b; b = temp; 千万不能写成 a = b; b = a;，那样两个数会变成一样的。可以把 temp 想象成一个空杯子，先把 a 倒进空杯，再让 a 变成 b，最后把空杯里的 a 倒给 b。
数组下标越界
内层循环中要比较 arr[j] 和 arr[j+1]，所以 j+1 最大是 n-1，对应的 j 最大是 n-2。如果写成 j < n，最后 j = n-1 时，arr[j+1] 会访问到数组外的内存，程序可能崩溃。正确是 j < n - 1 - i，保证不越界。

完整可运行的代码示例

下面是一个完整的 C++ 程序，它读入5个数字，用冒泡排序从小到大排好，然后输出结果。你可以在自己的电脑上运行试试。

#include <iostream>
using namespace std;

int main() {
    int arr[] = {5, 2, 9, 1, 7};  // 待排序的数组
    int n = 5;                    // 数组长度

    // 外层循环：控制排序的轮数，最多 n-1 轮
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;     // 标记本轮是否有交换，初始为 false

        // 内层循环：比较相邻元素，范围逐渐缩小
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 如果前一个比后一个大，交换它们
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;   // 发生了交换，标记改为 true
            }
        }

        // 如果本轮没有交换，说明已经排好，提前结束
        if (!swapped) {
            break;
        }
    }

    // 输出排序后的数组
    cout << "排序后的结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

运行结果：

排序后的结果：1 2 5 7 9

你也可以把数组改成你们班的考试成绩或者零花钱数目，看看冒泡排序是不是总能帮他们排好队。

冒泡排序：像汽水冒泡一样把数字排好