冒泡排序每轮遍历将当前未排序部分最大值移至末尾，故第i轮后末尾i个元素有序；内层循环上限应为n-1-i以防越界，使用std::swap更安全，但最坏时间复杂度仍为O(n²)。
冒泡排序为什么每次遍历后末尾元素就“到位”了
因为冒泡过程本质是相邻比较+交换，每轮完整扫描都会把当前未排序部分的最大值“浮”到最右端。所以第 i 轮结束后，末尾 i 个位置已有序，下一轮只需检查前 n - i 个元素。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 外层循环控制轮数，从
0到n-1，但内层循环上限应动态缩小：用j 替代固定 <code>j - 避免越界：若数组长度为
n，arr[j]和arr[j+1]合法要求j+1 ，即 <code>j —— 动态上限必须满足这点 - 错误写法示例：
for (int j = 0; j 可能导致访问 <code>arr[n-i]越界（当i=0时变成j ）
如何检测是否提前完成排序并跳出循环
如果某轮内层循环一次交换都没发生，说明整个数组已有序，后续轮次纯属浪费。这是最常用也最有效的剪枝手段。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 每轮开始前设
bool swapped = false；每次执行swap后置为true - 该轮结束后检查
swapped，为false就break外层循环 - 注意变量作用域：
swapped必须在轮次循环内定义，否则会累积上一轮状态 - 不加此判断时，最好情况（已排序数组）时间复杂度仍是
O(n²)；加了之后降为O(n)
优化版代码长什么样（C++11 及以后）
下面是一个兼顾可读性、安全性与常见优化点的实现，使用 std::vector 和范围 for 风格仅作示意，核心逻辑仍基于下标：
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;
}
}
关键点：
-
n - 1 - i是内层上限，不是n - i—— 否则j+1可能越界 - 用
std::swap比手写临时变量更安全，尤其对自定义类型 - 参数用非 const 引用，允许原地修改；若不想改原数组，需传值或加
const并返回新容器
什么时候不该用这个优化，或者它根本没用
优化只影响最好和平均情况下的常数因子或提前终止机会，最坏情况（逆序）仍要跑满 O(n²)。实际工程中，它几乎从不用于生产环境。
容易被忽略的地方：
- 对小数组（
n ），优化带来的分支预测失败可能比多几次比较还慢 - 现代 CPU 对连续内存访问友好，但频繁的
swap仍涉及三次赋值，不如插入排序局部性好 - 若数据是链表或随机访问代价高（如某些自定义迭代器），冒泡本身就不合适 —— 它严重依赖
O(1)下标访问 - 调试时加
swapped标志反而掩盖逻辑错误：比如本该交换却因条件写错没触发，程序“看似”提前结束了
