普通冒泡排序在已排序数组上仍需O(n²)时间，因其无提前终止机制；优化版引入swapped标志位，每轮重置为false，若未交换则提前退出。
为什么普通冒泡排序在已排序数组上仍要 O(n²) 时间
因为标准实现没有提前终止机制：即使输入已是升序，它仍会完整执行 n-1 轮比较，每轮都遍历剩余未排序段。时间复杂度退化为最坏情况，实际运行毫无必要。
带标志位的冒泡排序怎么写（C++ 基础版）
核心是引入布尔变量 swapped，每轮开始置为 false，只要发生一次交换就设为 true；若某轮结束仍为 false，说明全程无交换 → 数组已有序，直接跳出循环。
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时应直接返回，避免空循环或越界访问 - 内层循环上限用
n - 1 - i而非n - i：第i轮后，末尾i个元素已就位，无需再比 - 标志位必须在每轮**开头重置**为
false，否则会继承上一轮状态，导致提前退出
什么时候该换别的排序算法
即使加了标志位，冒泡排序最坏和平均时间复杂度仍是 O(n²)，且常数因子大。真实项目中：
– 小数组（n < 20）可接受，但 std::sort 通常更快（introsort 实现）
– 中等以上规模必须换 std::sort 或手写快排/归并
– 若需稳定且原地，可考虑插入排序（对小数组或基本有序数据更优）
