冒泡排序

冒泡排序是一种基于比较的排序算法：它反复比较相邻元素，并在元素不符合升序时交换它们。每次完整遍历结束后，未排序部分中的最大值都会移到右侧的最终位置。算法名称描述的正是元素在列表中反复移动的过程。冒泡排序易于跟踪和实现，但平方级的运行时间使它不适合大型集合。

冒泡排序算法

对于包含 n 个元素的数组 A，先比较 A[0] 和 A[1]，再比较 A[1] 和 A[2]，如此继续遍历未排序部分。只要左侧的值大于右侧的值，就交换二者。这个条件会得到升序结果；若要按降序排序，则反转比较条件。

每一轮都会从左向右遍历一次。遍历结束时，已访问部分中的最大值位于右边界，因此下一轮可以少检查一个位置。第一轮检查 n - 1 对元素，下一轮检查 n - 2 对，之后依此递减。固定轮数的实现会执行 n - 1 轮，即使最后一轮只需检查一对元素也是如此。少于两个元素的列表无需比较。

冒泡排序算法示例

以输入 (5, 3, 4, 2, 1) 为例。第一轮按顺序比较相邻元素：交换 5 和 3，得到 (3, 5, 4, 2, 1)；交换 5 和 4，得到 (3, 4, 5, 2, 1)；交换 5 和 2，得到 (3, 4, 2, 5, 1)；接着交换 5 和 1，得到 (3, 4, 2, 1, 5)。此时最大值已固定在最右侧。

第二轮只遍历前四个值，得到 (3, 2, 1, 4, 5)。第三轮将这个未排序前缀变为 (2, 1, 3, 4, 5)，第四轮再将其变为 (1, 2, 3, 4, 5)。这个过程说明了为什么每轮结束后未排序范围都会缩小，以及为什么已固定位置的值不会再次参与比较。

冒泡排序在 C++ 中的实现

下面的完整程序会原地排序示例。内层循环的上界 n - i - 1 可避免比较已经排好的后缀；条件 values[j] > values[j + 1] 会交换顺序错误的相邻元素，使较小的值向左移动。

运行此示例：

本节中的代码以及显示的标签或输出仍为英文。

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> values{5, 3, 4, 2, 1};
    bubble_sort(values);
    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Sorted: 1 2 3 4 5

提供的运行证据显示，该示例已成功运行，并在英文标签 Sorted: 后输出排好序的值 1 2 3 4 5。代码中的标签保持英文。

冒泡排序的复杂度与局限性

无论输入排列顺序如何，固定轮数的实现都会进行 (n - 1) + (n - 2) + ... + 1 次比较，也就是 n(n - 1) / 2 次。因此，它的最佳、平均和最坏时间复杂度均为 O(n²)。最坏情况下（例如输入按降序排列），还需要进行大量交换。该实现直接修改向量，交换时只使用一个临时值，因此辅助空间复杂度为 O(1)。

提前退出的变体可以记录每轮是否发生过交换；如果某轮结束后列表没有变化，就可以停止。对于已经排好序的输入，这种变体的运行时间为 O(n)，平均和最坏情况仍为 O(n²)。上面的固定轮数代码没有采用这种优化。冒泡排序适合用于学习相邻比较，也适用于非常小的输入；对于较大的集合，通常更适合使用标准库排序算法。