今天，我们要来聊一聊几乎所有程序员接触的第一个排序算法——冒泡排序（Bubble Sort）。
虽然在实际的工程开发中，冒泡排序因为效率问题很少被直接作为首选，但它绝对是理解“交换排序”思想的最佳入门教材。今天，我们就来拆解这个经典算法，并看看如何用 Java 写出一个“聪明”的冒泡排序。
核心思想：水底的气泡
冒泡排序的名字非常形象。你可以把待排序的数组想象成一个竖直的水池，数组左边是池底，右边是水面。数组里的每一个元素都是一个“气泡”，元素的值越大，气泡就越“重”。
它的核心运行机制就是相邻元素两两比较：
1、从头开始： 从数组的最左侧（第一个元素）开始，比较相邻的两个元素。
2、两两交换： 如果左边的元素比右边的大（即前一个比后一个大），就把它们俩交换位置。
3、一轮浮出： 这样一路比较和交换下去，一轮操作结束后，当前未排序部分中最大的那个元素，就会像气泡一样“浮”到数组的最右端（正确的位置）。
4、重复循环： 排除掉已经排好序的末尾元素，对剩下的元素重复上述过程，直到没有任何元素需要交换为止。
代码实现（含进阶优化）
常规的冒泡排序无论数组是否有序，都会傻傻地执行完所有的循环。为了体现我们的专业性，这里的加入了一个 swapped 标志位进行优化。如果某一轮遍历中没有发生任何交换，说明数组已经完全有序，我们可以直接提前下课！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| public class BubbleSortDemo {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
System.out.println("排序前：");
printArray(arr);
bubbleSort(arr);
System.out.println("排序后：");
printArray(arr);
}
/**
* 冒泡排序（优化版）
* @param arr 待排序数组
*/
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环：控制需要进行多少轮冒泡
for (int i = 0; i < n - 1; i++) {
// 优化标志位：记录本轮是否发生了数据交换
boolean swapped = false;
// 内层循环：负责相邻元素的比较和交换
// 注意边界 n - 1 - i：因为每一轮结束后，最后的 i 个元素已经是有序的了，无需再比
for (int j = 0; j < n - 1 - i; j++) {
// 如果前面的元素大于后面的元素，则交换
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true; // 发生了交换，修改标志位
}
}
// 如果这一轮从头到尾都没有发生过交换，说明数组已经完全有序了
// 直接跳出外层循环，提前结束算法！
if (!swapped) {
break;
}
}
}
/**
* 交换数组中两个元素的方法
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 打印数组辅助方法
*/
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
|
核心代码解析：
1、外层循环边界 (i < n - 1)： 既然每次能排好一个最大值，那么 $N$ 个元素的数组，排好 $N-1$ 个最大值后，剩下的最后那个（也就是最小的）自然就在第一位了，所以只需循环 $N-1$ 次。
2、内层循环边界 (j < n - 1 - i)： 这是冒泡排序的一个关键细节。随着外层循环 i 的增加，数组末尾已经排好序的元素越来越多。我们不需要再去比较那些已经归位的“大气泡”，所以每次内层循环的终点都要减去 i。
3、提前退出机制 (swapped)： 这个布尔变量是优化的灵魂。如果没有它，即使传入一个完全排好序的数组 [1, 2, 3, 4, 5]，算法也会强行做完所有的比较，纯属浪费时间。