Bubble Sort 冒泡排序 · BubbleSort.cpp
最基础的比较排序：每轮把相邻两个元素比一遍，大的往右挪。每一轮都有一个最大值"冒"到末尾
当然也可以写成向左挪的
一、复杂度与特性
| 项目 | 值 | 说明 |
|---|---|---|
| 时间（最好） | O(n) | 数据已有序时，一轮下来没有交换，靠swapped 直接退出 |
| 时间（平均 / 最坏） | O(n²) | 逆序是最坏情况，比较次数恰好 n(n-1)/2 |
| 空间 | O(1) | 原地排序，只有swapped 一个额外布尔量 |
| 稳定性 | 稳定 | 相等时不交换，同值元素的相对顺序不变 |
| 最坏交换次数 | n(n-1)/2 | 每一对逆序都要换一次 |
二、代码
void bubble_sort(std::vector<int> &a)
{
const int n = static_cast<int>(a.size());
for (int i = 0; i < n - 1; ++i)
{
bool swapped = false;
for (int j = 0; j < n - 1 - i; ++j)
{
if (a[j] > a[j + 1]) // 比较大小，如果该元素大于下一个元素就交换位置，得出的数组是升序的
{
std::swap(a[j], a[j + 1]);
swapped = true; // 标记有交换操作
}
}
if (!swapped)
break; // 这一轮没有任何交换 ⇒ 已经有序，直接退出排序
}
}要点：
- 内层边界是
n - 1 - i：末尾的i个元素已经就位，不用再进行比较 swapped提前退出a[j] > a[j+1]相等不交换，所以相同值的元素不会被交换
附件下载
可以直接取用这两个文件（右键另存为，或点击下载）：
完整可编译实现（含 sort_test 测试入口，32 行）（926 B）
本页笔记的 Markdown 原文（43 行，方便离线保存）（2 KB）