数据结构与算法 / 系统课时
冒泡排序
冒泡排序
冒泡排序通过反复比较相邻元素,把较大的元素逐步交换到数组右端。本课将跟踪每一轮的有序边界,加入提前终止标记,并分析该优化为什么能让已排序输入在线性时间内完成。
学习目标
- 描述冒泡排序中相邻比较与交换的执行过程。
- 实现带提前终止优化的 Java 冒泡排序。
- 判断冒泡排序的复杂度、稳定性和适用限制。
问题定义
给定一个数组,若相邻两个元素满足左侧大于右侧,就交换它们。完整扫描一轮后,本轮遇到的最大元素会移动到未排序区间最右端,因此下一轮无需再次访问这个已经确定的位置。

核心原理
第 i 轮结束后,数组末尾至少有 i + 1 个元素已经位于最终位置。于是内层循环的右边界可以写成 n - 1 - i,避免重复比较已确定区间。
冒泡排序的提前终止依赖布尔变量 swapped。每轮开始时将其设为 false;只要发生交换就改为 true。若一轮扫描结束后仍为 false,说明当前数组已经有序,可以立即结束外层循环。
为了保持稳定性,交换条件必须使用严格大于 >。若写成大于等于 >=,两个相等元素也会交换,从而可能改变它们的原始先后顺序。
带提前终止的冒泡排序在数组已经有序时只需完成一轮扫描,最好时间复杂度为 O(n);对互异键的均匀随机排列,平均为 Θ(n²),最坏也为 Θ(n²),额外空间复杂度为 O(1)。
完整可运行示例
下面的程序统计实际执行的轮数、比较次数和交换次数。将代码保存为 BubbleSortDemo.java。
import java.util.Arrays;
public class BubbleSortDemo {
public static void main(String[] args) {
int[] values = {5, 1, 4, 2, 8};
SortStats stats = bubbleSort(values);
System.out.println("排序结果: " + Arrays.toString(values));
System.out.println("执行轮数: " + stats.passes);
System.out.println("比较次数: " + stats.comparisons);
System.out.println("交换次数: " + stats.swaps);
}
static SortStats bubbleSort(int[] values) {
int passes = 0;
long comparisons = 0;
long swaps = 0;
for (int i = 0; i < values.length - 1; i++) {
boolean swapped = false;
passes++;
// 右侧 i 个元素已经位于最终位置,无需再次比较。
for (int j = 0; j < values.length - 1 - i; j++) {
comparisons++;
if (values[j] > values[j + 1]) {
int temp = values[j];
values[j] = values[j + 1];
values[j + 1] = temp;
swaps++;
swapped = true;
}
}
// 本轮没有交换,说明整个数组已经有序。
if (!swapped) {
break;
}
}
return new SortStats(passes, comparisons, swaps);
}
static class SortStats {
final int passes;
final long comparisons;
final long swaps;
SortStats(int passes, long comparisons, long swaps) {
this.passes = passes;
this.comparisons = comparisons;
this.swaps = swaps;
}
}
}运行命令
javac -encoding UTF-8 BubbleSortDemo.java
java BubbleSortDemo预期输出
排序结果: [1, 2, 4, 5, 8]
执行轮数: 3
比较次数: 9
交换次数: 4优化效果与边界
| 输入状态 | 是否提前终止 | 时间复杂度 |
|---|---|---|
| 已经升序 | 第一轮后终止 | O(n) |
| 基本有序 | 可能较早终止 | 取决于逆序分布 |
| 逆序 | 无法提前终止 | O(n^2) |
提前终止只减少不必要的后续轮次,不会改变逆序输入需要大量相邻交换的事实。每次只交换严格逆序的相邻两项,整个序列的严格逆序对恰好减少一个,所以交换总数等于初始逆序对数。但比较数还与逆序位置有关。比如 [5,1,2,3,4] 和 [2,3,4,5,1] 都有 4 个逆序对。前者执行 2 轮、比较 7 次,后者执行 4 轮、比较 10 次,因为小元素每轮最多向左移动一格。
Tips
- 每轮开始时必须重新设置
swapped = false,否则旧状态会让提前终止失效。 - 内层上界使用
values.length - 1 - i,既防止访问j + 1越界,也跳过已确定区间。 - 若只需判断数组是否有序,可复用“一轮无交换”的思想,但不必执行完整排序。
常见错误
1. 忘记缩小右边界
始终扫描到数组末尾不会影响排序正确性,却会重复比较已经确定的元素。应让每轮的比较上界随 i 减小。
2. 使用大于等于作为交换条件
条件 values[j] >= values[j + 1] 会交换相等元素,破坏稳定性。升序冒泡排序应使用 values[j] > values[j + 1]。
本课练习
- 用至少两个元素的非递减数组验证一轮、n−1 次比较和零交换。用空数组及单元素验证零轮、零比较。
- 扩展统计信息,输出每一轮结束后的数组状态,但不得改变排序结果和提前终止逻辑。
本课总结
- 冒泡排序通过相邻交换,把当前最大元素逐轮推到未排序区间末端。
swapped标记可让有序输入在O(n)时间内结束,但最坏复杂度仍为O(n^2)。- 使用严格大于条件时算法稳定,但频繁交换限制了它在大规模数据上的实用性。
下一课预告
下一课学习归并排序,将任务拆成两个有序子序列再线性合并,并比较所需辅助空间。