冒泡排序动画

算法原理

冒泡排序（Bubble Sort）是最直观的排序算法之一：它反复扫描序列，依次比较相邻的两个元素，如果顺序错误就把它们交换过来。每一轮扫描结束后，未排序部分中最大的元素就像水中的气泡一样“浮”到未排序区间的末尾，因此得名。

对长度为 n 的序列，冒泡排序的执行过程是：

1. 第 1 轮：从下标 0 开始，依次比较 (0,1)、(1,2)、…、(n-2,n-1) 相邻元素对，把最大值换到下标 n-1；
2. 第 2 轮：对前 n-1 个元素重复上述过程，把次大值放到下标 n-2；
3. 以此类推，每轮未排序区间缩短一格，共进行最多 n-1 轮后整个序列有序。

动画怎么看

柱子颜色就是状态语言（页面右侧也有图例）：

• 金色柱：当前正在比较的一对相邻元素；
• 红色柱：刚发生交换的一对，下一拍就会恢复；
• 绿色柱：已就位的后缀——每轮结束最大的元素落到末尾，绿色区间从右往左生长；
• 蓝色柱：尚未处理的元素。

动画下方有一行实时解说（如 a[2] > a[3]，交换 9 ↔ 1），结束时汇总总比较次数与交换次数，可以直观感受 O(n²) 的比较规模；右侧滑块可调节播放速度。

复杂度分析

C++ 参考代码

#include <iostream>
#include <vector>
#include <utility>  // std::swap
using namespace std;

// 冒泡排序：带提前退出优化的写法
void bubbleSort(vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {          // 最多 n-1 轮
        bool swapped = false;
        for (int j = 0; j + 1 < n - i; j++) {  // 未排序区间内两两比较
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);          // 大的往后冒
                swapped = true;
            }
        }
        if (!swapped) break;                   // 本轮无交换 → 已有序，提前结束
    }
}

int main() {
    vector<int> a = {5, 2, 9, 1, 7, 3, 8, 4};
    bubbleSort(a);
    for (int x : a) cout << x << ' ';          // 输出：1 2 3 4 5 7 8 9
    cout << endl;
    return 0;
}

什么时候用冒泡排序

冒泡排序时间复杂度是 O(n²)，在大数据量下远慢于快速排序、归并排序等 O(n log n) 算法，实际工程中很少直接使用。但它交换相邻元素的形式非常简单，是理解排序过程与复杂度分析的最佳入门案例；在 CSP-J 入门阶段，也常作为「逐轮模拟」类题目的基础套路出现。