冒泡排序（Bubble Sort）是一种简单但直观的排序算法，常作为学习排序算法的入门案例。本文将详细介绍冒泡排序的原理、实现方式，并通过一个例子展示排序的全过程。
一、冒泡排序的基本原理
冒泡排序的工作方式类似于水中的气泡，从底部不断向上冒。在一轮比较中，较大的元素会逐步“冒泡”到列表的末尾。
核心思想：
每次遍历相邻的两个元素，如果前一个比后一个大，就交换它们的位置。
通过多次遍历，每轮将当前未排序部分中的最大值“冒泡”到末尾。
随着遍历次数增加，未排序部分逐渐减少，最终整个序列变为有序。
二、冒泡排序的伪代码
步骤描述：
对数组进行多轮遍历。
每次从头到尾比较相邻的两个元素。
如果发现逆序（即前一个元素大于后一个元素），就交换这两个元素。
当一轮遍历完成后，最大元素会被放到最后。
重复上述过程，直到所有元素有序。
三、冒泡排序的代码实现
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped; // 标志变量，用于优化
for (int i = 0; i < n - 1; i++) { // 外层循环控制轮次
swapped = false; // 每轮开始时重置标志
for (int j = 0; j < n - 1 - i; 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;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 2};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
bubbleSort(arr);
System.out.println("排序后：" + java.util.Arrays.toString(arr));
}
}
代码解读：
外层循环 i 控制需要进行的排序轮次，每轮将最大的元素放到末尾。
内层循环 j 负责比较相邻的元素并交换。
优化：引入 swapped 标志变量。如果在某轮中没有发生交换，说明数组已排序，可提前结束。
四、冒泡排序过程详解
假设我们需要对数组 [5, 3, 8, 6, 2] 进行升序排序。
轮次第 i 轮排序后的数组过程描述初始[5, 3, 8, 6, 2]初始状态，未排序。第 1 轮[3, 5, 6, 2, 8]比较并交换：5 > 3 -> 交换，8 > 6 -> 交换，8 > 2 -> 交换，8 被放到正确位置。第 2 轮[3, 5, 2, 6, 8]比较并交换：5 > 2 -> 交换，6 已位于正确位置，无需动。第 3 轮[3, 2, 5, 6, 8]比较并交换：3 > 2 -> 交换，5 已位于正确位置，无需动。第 4 轮[2, 3, 5, 6, 8]此轮没有发生交换，排序完成，提前结束。
五、时间复杂度与优化
时间复杂度：
最坏时间复杂度：O(n^2)
当数组是逆序时，需要进行最多的比较和交换。
最佳时间复杂度：O(n)
当数组已经有序时，内层循环不会发生交换，标志变量 swapped 能及时终止外层循环。
平均时间复杂度：O(n^2)
空间复杂度：
冒泡排序是原地排序算法，只需常数级额外空间，空间复杂度为 O(1)。
优化：
通过引入标志变量 swapped，当一轮比较后没有发生交换时，提前退出算法，从而提高效率。
六、冒泡排序的优缺点
优点：
实现简单，容易理解。
对少量数据表现良好，适合作为入门学习算法。
缺点：
时间复杂度高，不适合处理大量数据。
即使数组已部分有序，仍需要完整比较（优化后可减少）。
七、总结
冒泡排序虽然效率不高，但通过学习它，我们可以掌握排序算法的基本思想和实现技巧。它的优化版本也能在部分情况下表现出较好的性能。作为入门级排序算法，冒泡排序为后续理解更复杂的排序方法（如快速排序、归并排序）打下了坚实的基础。
希望通过这篇博客，您能对冒泡排序的原理、实现和优化有全面的理解！如果对排序算法有其他疑问，欢迎留言讨论。
PS：可以点击打开“冒泡排序算法演示”页面亲自体验一下 😊
文章导航
插入排序（Insertion Sort）