优化版冒泡排序通过布尔哨兵标志判断是否发生交换，若某轮无交换则立即终止循环，使最好时间复杂度降至o(n)，空间复杂度仍为o(1)。
在 Java 中实现冒泡排序的优化版，核心是引入“是否发生交换”的哨兵变量（通常用 boolean 类型），一旦某轮遍历中没有元素交换，说明数组已有序，可立即终止外层循环，避免无效比较。
基本思路：用布尔哨兵判断是否提前结束
标准冒泡排序无论数组是否已有序，都会执行 n−1 轮比较。优化的关键在于：每轮内层循环后检查是否有交换发生。若无交换，说明排序完成，跳出外层循环。
注意：这个哨兵不是数组里的某个“占位元素”（如哨兵值 -1），而是逻辑上的状态标记，因此更准确叫“哨兵标志”或“提前终止标志”。
代码实现（含详细注释）
public static void bubbleSortOptimized(int[] arr) {
if (arr == null || arr.length
int n = arr.length;
for (int i = 0; i
boolean swapped = false; // 哨兵标志：本轮是否发生交换
// 每轮把最大元素“冒泡”到末尾，未排序区长度为 n - i - 1
for (int j = 0; j
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // 发生交换，更新哨兵
}
}
// 关键优化：若本轮没交换，说明已有序，直接退出
if (!swapped) {
break;
}
}
}
为什么这叫“哨兵位”？它不是数组元素
这里容易误解：“哨兵位”不是在数组开头或末尾加一个特殊值（比如 Integer.MAX_VALUE），而是在控制逻辑中设置一个布尔变量作为运行时的“守卫信号”。它的作用是监听排序进程状态，一旦满足条件（!swapped）就触发提前返回——就像哨兵发现异常就立刻报警一样。
- 不修改原数组结构，空间复杂度仍为 O(1)
- 最好情况时间复杂度从 O(n²) 降到 O(n)（输入已升序）
- 最坏和平均仍是 O(n²)，但实际运行常数更小
测试验证优化效果
可分别用以下数组测试：
-
已排序数组：
{1, 2, 3, 4, 5}→ 只执行 1 轮内循环，随后 swapped = false，立即退出 -
逆序数组：
{5, 4, 3, 2, 1}→ 执行全部 4 轮，每轮都有交换，哨兵不生效 -
部分有序数组：
{1, 3, 2, 4, 5}→ 第 2 轮后即有序，第 3 轮检测到 swapped == false 终止
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
