标准冒泡排序用两层for循环实现：外层控制n-1轮，内层逐对比较相邻元素并交换，确保每轮最大值沉底；常见错误是内层边界误写为i而非n-1-i。
冒泡排序的 C++ 基础实现长什么样
标准冒泡排序就是两层 for 循环，外层控制轮数（最多 n-1 轮），内层逐对比较相邻元素并交换。关键在于「相邻」和「每轮后最大值沉底」这个逻辑。
常见错误是内层循环边界写成 i 导致越界，或漏掉 swap 后的边界收缩（每轮后末尾已有序，可缩短比较范围）：
void bubbleSort(vector& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - 1 - i; ++j) { // 注意：上限是 n-1-i，不是 n-1 if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } }
怎么提前终止优化冒泡排序
如果某一轮内一次交换都没发生，说明数组已完全有序，后续轮次纯属浪费。加个标志位就能让最好情况时间复杂度从 O(n²) 降到 O(n)。
容易忽略的是：标志位必须在每轮开始前重置为 false，否则会误判；且不能只靠外层 i 判断是否提前退出。
立即学习“C++免费学习笔记（深入）”；
- 用
bool swapped = false记录本轮是否有交换 - 每次交换后设为
true - 本轮结束若仍是
false，直接break
void bubbleSortOptimized(vector& 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]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; // 没交换，已有序 } }
C++ 中 vector 和原生数组写法有啥区别
核心逻辑一致，但传参方式和长度获取不同。用 vector 更安全（自动管理内存、支持 .size()），而原生数组传参会退化为指针，必须额外传长度。
常见坑是把数组名直接传给函数却没传 len，导致无法知道边界；或者误用 sizeof(arr)/sizeof(arr[0]) 在函数内部计算长度（此时 arr 是指针，结果恒为 1 或 2）。
- 原生数组推荐签名：
void bubbleSort(int arr[], int len) - 别在函数里用
sizeof算长度 - 迭代器版本更泛型，但初学易绕晕，不建议一上来就写
为什么它被列为“经典”却不该在实际项目中用
冒泡排序教学价值远大于实用价值。它的 O(n²) 时间复杂度、频繁的交换操作（比快排/归并多得多）、以及无法利用 CPU 缓存局部性，让它在任何稍大点的数据集上都明显慢于 std::sort（通常是 introsort，平均 O(n log n)）。
真正要注意的是：面试写冒泡时，考官往往看的是你能否指出它的缺陷、能否写出带提前终止的版本、能否对比它和插入排序的异同——而不是只默写一个能跑通的循环。
如果你真在工程代码里写了冒泡排序，而且数据量超过几百，那问题大概率不在算法本身，而在你没搞清需求或没查 STL 文档。
