冒泡排序最简C++实现为两层循环：外层i从0到n-2，内层j从0到n-2-i，比较arr[j]与arr[j+1]并手动交换；优化版增加swapped标志位，若某轮无交换则提前退出。
冒泡排序的最简 C++ 实现
直接写 std::vector 版本，不封装类、不搞模板泛化，就是为快速验证逻辑或教学演示用。
- 核心是两层循环：外层控制轮数（最多
n-1轮），内层做相邻比较交换 - 每次内层循环后，最大元素“冒泡”到末尾，所以内层上限可逐步缩小
- 别用
std::swap包裹单个int交换——原生赋值更快，且避免隐式类型转换风险
void bubble_sort(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 tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
加提前退出的优化版（检测是否已有序）
原始冒泡在最好情况（输入已升序）下仍是 O(n²)，加一个标志位就能降到 O(n)，实际中很值得加。
- 每轮开始前设
swapped = false，只要发生一次交换就置为true - 某轮结束时若
swapped仍为false，说明全程没换过，数组已有序，直接break - 注意：这个优化不影响最坏/平均时间复杂度，但对部分有序数据提升明显
- 别把标志位声明在最外层循环外又忘记重置——这是新手高频错误
void bubble_sort_optimized(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;
}
}
if (!swapped) break;
}
}
为什么不用 std::sort？什么场景还值得手写
std::sort 是混合排序（introsort），平均 O(n log n)，远快于冒泡；但手写冒泡不是为了性能，而是明确控制行为。
- 教学/面试：考察基础循环、边界理解和稳定性的直觉
- 嵌入式小内存环境：没有 STL 支持，或禁止动态分配，纯栈操作更可控
- 需要稳定排序且必须自定义比较逻辑，又不想引入完整算法库时，冒泡改写成本最低
- 千万别在生产代码里用它处理 >1000 元素的数组——哪怕加了优化，O(n²) 的常数因子也大得离谱
容易被忽略的边界和陷阱
看似简单，但 C++ 里几个细节一错就段错误或逻辑错。
立即学习“C++免费学习笔记（深入）”；
-
arr.size()返回size_t（无符号），和负数i混用会引发隐式转换问题——务必转成int或用有符号索引变量 - 内层循环上限写成
j < n - i是错的，应是j < n - 1 - i，否则arr[j + 1]会越界 - 如果传入空
vector或单元素，n - 1可能为 0 或负，但循环条件自然不满足，实际安全；不过显式加if (n <= 1) return;更清晰 - 别对
std::list或其他非随机访问容器用这套逻辑——冒泡依赖O(1)下标访问，链表会退化成 O(n³)
手写冒泡真正难的不是交换逻辑，而是把每一轮的边界缩进、提前退出判断、类型安全这三件事同时做对。调试时多打一行 std::cout << "round " << i << ", max=" << arr.back() << "\n"; 就能省掉大半困惑。
