C++ 冒泡排序

假设现在有一组打乱的数字：5、3、8、4、2，如果每次只允许比较相邻的两个数字，我们怎样才能把它们按从小到大的顺序排好呢？“冒泡排序” 就是专门采用这种思路来排序的经典算法。

它的基本动作非常直观：从左往右依次比较相邻的两个元素，如果前一个数比后一个数大，就把它们交换位置。这样从头到尾走完第 1 轮后，最大的数字 8 就会像水底的气泡一样，一步步向右移动并 “冒” 到最末尾的位置，如下图所示。

冒泡排序的工作原理

在动手写代码之前，我们先拿这 5 个数字试排一遍，顺着第 1 轮的 4 次相邻比较看看序列是怎么变化的：

初始序列：5, 3, 8, 4, 2
比较 5 和 3：3, 5, 8, 4, 2
比较 5 和 8：3, 5, 8, 4, 2
比较 8 和 4：3, 5, 4, 8, 2
比较 8 和 2：3, 5, 4, 2, 8

经过第 1 轮的 4 次相邻比较后，最大的数字 8 已经归位到了最右边，下一轮就不需要再把 8 算进去了。顺着这个规律往下推：第 2 轮只需对前面剩下的 4 个数比较 3 次就能排好 5，第 3 轮比较 2 次排好 4，第 4 轮比较 1 次排好 3，此时剩下的最小数 2 自然就在最左边了。

推广到包含 n 个元素的序列，我们可以使用双层 for 循环来组织整个排序过程，两层循环的具体分工如下：

• 外层循环：用来控制排序轮数 i（从 0 开始计数）。每走完一轮就能确定一个较大数的位置，把前 n - 1 个数归位后整个序列就排好了，因此我们让 i 从 0 循环到 i < n - 1（共执行 n - 1 轮）。
• 内层循环：用来控制相邻比较的下标 j。当外层处于下标 i 时，最右边已经有 i 个元素排好序了，因此我们让 j 从 0 循环到 j < n - 1 - i，每次比较 arr[j] 和它右边的 arr[j + 1]。

我们可以拿元素个数 n = 5 代入验证一下：第 1 轮 i = 0 时，内层条件是 j < 4（比较 4 次）。到了第 2 轮 i = 1 时，内层条件变成 j < 3（比较 3 次），刚好每一轮都比上一轮少比较 1 次。

使用双层 for 循环实现冒泡排序

下面我们将冒泡排序写成 bubbleSort() 函数，对传入的 vector 容器按从小到大的顺序排序。需要注意的是，函数形参 std::vector<int>& arr 使用了引用传递，这样在函数内部交换元素时，才能直接修改外部传入的原容器。

示例 1：实现基础冒泡排序

#include <iostream>
#include <vector>

// 按从小到大冒泡排序
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    // 外层循环控制排序轮数
    for (int i = 0; i < n - 1; i++) {
        // 内层循环比较相邻元素
        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;
            }
        }
    }
}

int main() {
    std::vector<int> arr = {5, 3, 8, 4, 2};
    bubbleSort(arr);

    std::cout << "排序后的结果：";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

排序后的结果：2 3 4 5 8

分析：

内层循环里的 if (arr[j] > arr[j + 1]) 表示判断相邻两个元素是不是 “前大后小”。一旦发现左边元素大于右边元素，我们就先借助临时变量 temp 把 arr[j] 的旧值保存起来。接着把 arr[j + 1] 赋给 arr[j]，最后再把 temp 赋给 arr[j + 1] 完成互换。

小伙伴们要特别留意内层循环的终止条件 j < n - 1 - i。为什么要减 1 呢？因为循环体里要访问 arr[j + 1]，一旦误写成 j < n，当 j 走到末尾下标 n - 1 时，arr[j + 1] 就会越界访问不存在的 arr[n]。在此基础上再减去 i，则是为了跳过末尾已经排好序的 i 个元素。

此外，函数开头先通过 int n = arr.size(); 将元素个数存入有符号的 int 变量 n。这样即使传入空容器，算出来的 n - 1 也是 -1，循环条件 i < -1 不成立便直接安全退出，不会因为无符号整数相减回绕而越界。

使用 bool 变量提前结束排序

小伙伴们可以思考一个问题：如果传进来的序列 1、2、3、4、5 本来就是排好序的，或者刚排完第 1 轮就已经全部有序了，会发生什么呢？按照上面示例 1 的写法，程序还是会把后面剩下的轮次全部跑完。

为了减少不必要的比较，我们可以在每一轮开始前定义一个布尔变量 swapped = false。只要当前这一轮发生过元素交换，就将 swapped 设为 true。如果一整轮从左到右比下来，一次交换都没有发生，说明整个序列已经完全有序了，此时直接使用 break 语句跳出外层循环即可。

示例 2：提前结束冒泡排序

#include <iostream>
#include <utility>                 // 提供 std::swap()
#include <vector>

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;      // 记录本轮是否发生交换
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;    // 发生交换则设为 true
            }
        }
        // 本轮未发生交换则提前结束
        if (!swapped) {
            break;
        }
    }
}

int main() {
    std::vector<int> arr = {1, 2, 4, 3, 5};
    bubbleSort(arr);

    std::cout << "排序后的结果：";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << '\n';
    return 0;
}

运行结果如下。

排序后的结果：1 2 3 4 5

分析：

在这个例子中，初始序列 {1, 2, 4, 3, 5} 只有中间的 4 和 3 顺序反了。第 1 轮比较时，程序将 4 和 3 交换成 3 和 4，并把 swapped 设为 true。

到了第 2 轮，序列已经是 {1, 2, 3, 4, 5}，内层循环从头比到尾没有发生交换。此时 if (!swapped) 成立，程序直接执行 break 结束排序，省去了第 3 轮和第 4 轮的重复检查。

大家在写这个优化时要注意，bool swapped = false; 必须放在外层循环的里面、内层循环的前面，这样每一轮开始时才会重新重置为 false。如果把它放到了外层循环外面，只要第 1 轮发生过交换，swapped 就会一直保持为 true，后面的提前结束判断也就起不到作用了。