冒泡排序的核心思想非常直观：通过重复地遍历数组，比较相邻的元素并交换顺序，让最大的元素像“气泡”一样逐渐“浮”到数组的末尾。
下面我为你详细解析其实现原理、代码以及优化方案。
📝 算法原理
1. 比较相邻：比较相邻的两个元素，如果前一个比后一个大（升序），就交换它们。
2. 一趟遍历：对数组从头到尾进行一次这样的比较，最大的元素就会被交换到数组的最后一位。
3. 重复操作：忽略已经排好序的最后一个元素，对剩余的元素重复上述过程。
4. 结束条件：当某一次遍历中没有发生任何交换时，说明排序完成。
💻 Java 代码实现
基础版本
public class BubbleSort {
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);
}
// 冒泡排序核心方法
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制排序的轮数 (n-1 轮即可排好)
for (int i = 0; i arr[j + 1]) {
// 交换元素
swap(arr, j, j + 1);
}
}
}
}
// 交换数组中两个位置的值
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 value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}
优化版本
优化点：如果在某一轮遍历中，没有发生任何交换，说明数组已经有序，无需再进行后续的比较。
public static void bubbleSortOptimized(int[] arr) {
int n = arr.length;
boolean swapped; // 标志位，记录本轮是否发生交换
for (int i = 0; i arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true; // 发生了交换，置为 true
}
}
// 如果本轮没有发生交换，提前结束
if (!swapped) break;
}
}
📊 复杂度分析
- 时间复杂度：
- 最坏情况：O(n^2) —— 数组完全逆序，需要进行 n(n-1)/2 次比较和交换。
- 最好情况：O(n) —— 数组已经有序，优化版本只需遍历一次即可发现无需交换。
- 平均情况：O(n^2)。
- 空间复杂度：O(1) —— 只使用了常数个额外变量（用于交换和标志位）。
- 稳定性：稳定 —— 相等的元素在排序后相对位置不会改变（因为只有在 > 时才交换，= 时不交换）。
🔄 执行过程演示
以数组 [5, 2, 4, 1, 3] 为例：
- 第 1 轮：[2, 4, 1, 3, 5] （5 冒泡到末尾）
- 第 2 轮：[2, 1, 3, 4, 5] （4 冒泡到倒数第二）
- 第 3 轮：[1, 2, 3, 4, 5] （3 冒泡到倒数第三）
- 第 4 轮：检查发现有序，结束。
📌 总结
冒泡排序虽然效率不高（O(n^2)），不适合处理大数据量，但它的逻辑非常简单，是学习排序算法的绝佳入门案例。在实际开发中，对于小数据量或教学演示，它依然非常有用。