每一趟相邻比较，若前一个大于后一个就交换。这样每一轮都能把当前最大元素"冒泡"到末尾。

Ph1zの理解： 想象水里的气泡——越大的气泡浮得越快。每一轮扫描，最大的元素就像气泡一样一路"冒"到最后面。名字就是这么来的喵

代码

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 早停：这趟没交换，已经有序
    }
}

正确性证明

循环不变式： 在一趟冒泡结束后，当前未排序区间的最大元素已经被放到区间末尾。

• 在一轮扫描中，如果 a[j] > a[j+1]，则交换，保证较大的元素向右移动。
• 经过整趟扫描，所有大于当前末尾元素的值都会被"冒"过去，因此最大值会落在末尾。
• 重复 $n-1$ 趟后（或早停），数组整体有序。 ✓

复杂度分析

情况	时间复杂度	直觉
最好	$O(n)$	已排序 + 早停：第一趟没有交换，直接结束
最坏	$\mathrm{\Theta }(n^2)$	逆序：每次比较都要交换
平均	$O(n^2)$	随机数据，约一半的比较需要交换

空间复杂度： $O(1)$。

稳定性： 稳定。因为只有 a[j] > a[j+1] 时才交换，相等元素不交换，顺序保持不变。

冒泡 vs 插入： 两者最好都是 $O(n)$，最坏都是 $O(n^2)$，都是稳定的。但插入排序的实际移动次数更少（只移动必要的元素），冒泡排序每次交换要 3 次赋值。实战中插入排序通常更快。