冒泡排序算法原理与Java实现¶
在编程中，排序是一项基础且常见的任务。冒泡排序（Bubble Sort）是最简单的排序算法之一，其核心思想是通过重复比较相邻元素并交换位置，使较大的元素“冒泡”到数组末尾（升序排序时），或较小的元素“冒泡”到数组开头（降序排序时）。
排序步骤解析¶
以数组 [5, 2, 9, 1, 5] 为例，演示升序排序过程：
-
第一轮（未排序部分：
[5,2,9,1,5]）
- 比较5和2：5 > 2，交换 →[2,5,9,1,5]
- 比较5和9：5 < 9，不交换
- 比较9和1：9 > 1，交换 →[2,5,1,9,5]
- 比较9和5：9 > 5，交换 →[2,5,1,5,9]
- 结果：最大元素9已“冒泡”到末尾，未排序部分变为[2,5,1,5] -
第二轮（未排序部分：
[2,5,1,5]）
- 比较2和5：2 < 5，不交换
- 比较5和1：5 > 1，交换 →[2,1,5,5]
- 比较5和5：5 = 5，不交换
- 结果：第二大元素5已“冒泡”到倒数第二位，未排序部分变为[2,1,5] -
第三轮（未排序部分：
[2,1,5]）
- 比较2和1：2 > 1，交换 →[1,2,5]
- 比较2和5：2 < 5，不交换
- 结果：第三大元素5已“冒泡”到倒数第三位，未排序部分变为[1,2] -
第四轮（未排序部分：
[1,2]）
- 比较1和2：1 < 2，不交换
- 结果：排序完成，数组变为[1,2,5,5,9]
Java代码实现¶
public class BubbleSort {
/**
* 冒泡排序算法实现（升序）
* @param arr 待排序的数组
*/
public static void bubbleSort(int[] arr) {
// 外层循环：控制排序轮数（最多n-1轮）
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false; // 优化标记：本轮是否发生交换
// 内层循环：控制每轮比较次数（已排好序的元素无需再比较）
for (int j = 0; j < arr.length - 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, 2, 9, 1, 5};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
// 调用冒泡排序
bubbleSort(arr);
System.out.println("排序后：" + java.util.Arrays.toString(arr));
}
}
代码关键点说明¶
- 外层循环：控制排序轮数，共需
arr.length - 1轮（最后一个元素无需比较）。 - 内层循环：每轮比较相邻元素，次数为
arr.length - 1 - i（i为已排好序的元素个数）。 - 交换逻辑：使用临时变量
temp交换相邻元素，确保排序稳定。 - 优化技巧：通过
swapped标记，若某轮无交换，提前终止排序（适用于接近有序的数组）。
时间与空间复杂度¶
- 时间复杂度：
- 最坏情况（完全逆序）：
O(n²)（需完整执行所有轮次）。 - 平均情况：
O(n²)。 - 最好情况（已排序）：
O(n)（优化后通过swapped标记提前终止）。 - 空间复杂度：
O(1)（仅需临时变量，原地排序）。
总结¶
冒泡排序原理简单直观，适合初学者理解排序核心思想。但由于时间复杂度较高（O(n²)），实际应用中较少用于大规模数据，通常用于教学或小规模数据排序场景。掌握后可进一步学习更高效的排序算法（如快速排序、归并排序等）。