冒泡排序算法完整详解（原理+排序过程+基础代码+优化代码）
本文目录如下：
一、冒泡排序核心基本思想
冒泡排序是一种基础的交换类排序算法。
核心规则：从前向后遍历待排序数组，依次比较相邻的两个元素，如果前一个元素大于后一个元素（逆序），则交换两者位置。每一轮遍历结束后，当前未排序区间的最大值会“冒泡”到未排序区间的末尾，如同水底气泡向上浮出水面，因此得名冒泡排序。
重复多轮遍历，直到所有元素全部有序。
1、时间复杂度（面试高频考点）
① 基础版冒泡排序（无优化）
- 最坏情况（数组完全逆序）：O(n²)，每一轮都需要全部比较+多次交换
- 最好情况（数组已有序）：O(n²)，无交换操作，但仍会完整执行所有循环比较，无法提前终止
- 平均情况：O(n²)
② 优化版冒泡排序（标志位优化）
- 最坏情况（数组完全逆序）：O(n²)，和基础版一致，需完整遍历比较交换
- 最好情况（数组已有序）：O(n)，仅遍历一轮、无交换，直接提前终止排序
- 平均情况：O(n²)
2、空间复杂度（面试高频考点）
① 基础版冒泡排序
空间复杂度为 O(1)，仅定义单个临时交换变量，无额外开辟数组、集合等存储空间，属于原地排序算法。
② 优化版冒泡排序
空间复杂度仍为 O(1)，仅额外新增一个布尔类型标志位变量，全程使用常数级临时空间，不随数据量n变化，同样属于原地排序算法。
O(1)，仅使用常数级临时变量，属于原地排序
二、数组分步排序演示（修正完整版）
待排序原始数组：[3，9，-1，10，20]，数组长度 n = 5
核心规律：n 个元素，最多需要 n-1 轮 排序；每一轮都会确定一个最大值的最终位置，后续轮次无需再遍历已排序的末尾元素。
第一轮排序（确定最大值 20）
遍历范围：全部5个元素，比较4次
3 和 9 比较：3 < 9，不交换 → [3,9,-1,10,20]
9 和 -1 比较：9 > -1，交换 → [3,-1,9,10,20]
9 和 10 比较：9 < 10，不交换 → [3,-1,9,10,20]
10 和 20 比较：10 < 20，不交换 → [3,-1,9,10,20]
第一轮结果：[3,-1,9,10,20]，最大值20已就位
第二轮排序（确定第二大值 10）
遍历范围：前4个元素 [3,-1,9,10]
3 和 -1 比较：3 > -1，交换 → [-1,3,9,10,20]
3 和 9 比较：3 < 9，不交换
9 和 10 比较：9 < 10，不交换
第二轮结果：[-1,3,9,10,20]，第二大值10已就位
第三轮排序（确定第三大值 9）
遍历范围：前3个元素 [-1,3,9]
-1 和 3 比较：不交换
3 和 9 比较：不交换
第三轮无交换，数组已经完全有序
第四轮排序（理论最后一轮）
遍历范围：前2个元素，无任何交换，数组保持有序
三、冒泡排序核心规律小结
1、排序总轮数：n-1 轮（n为元素个数，排完n-1个元素，最后一个元素自然有序）
2、每一轮比较次数逐轮递减：第 i 轮比较次数 = n-1-i
3、普通冒泡排序：无论数组是否提前有序，都会跑完所有循环，存在性能浪费
4、可优化：若某一轮排序没有发生任何元素交换，说明数组已经全局有序，可直接终止排序
四、基础版冒泡排序代码（双层循环标准版）
由分步推导整合为双层for循环，无优化，逻辑直观：
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {3, 9, -1, 10, 20};
int temp; // 临时变量，用于元素交换
// 外层循环：控制总排序轮数 n-1 轮
for (int i = 0; i < arr.length - 1; i++) {
// 内层循环：每一轮的两两比较，逐轮减少比较次数
for (int j = 0; j < arr.length - 1 - i; j++) {
// 前一个元素大于后一个，逆序则交换
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// 遍历输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
}
五、优化版冒泡排序（标志位提前终止）
问题：基础版数组提前有序后，仍会无效循环比较，浪费性能。
优化方案：定义交换标志位，记录每一轮是否发生交换，无交换则直接结束排序。
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {3, 9, -1, 10, 20};
int temp;
boolean flag; // 交换标志位：true=本轮发生交换，false=无交换
// 最多 n-1 轮排序
for (int i = 0; i < arr.length - 1; i++) {
flag = false; // 每一轮开始前，重置标志位为未交换
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 发生元素交换
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// 本轮无任何交换，数组已有序，直接退出循环
if (!flag) {
break;
}
}
// 输出结果
for (int num : arr) {
System.out.print(num + " ");
}
}
}
六、算法特点
1、简单易懂、代码实现简单
2、效率较低，不适合大数据量排序
3、优化后可针对有序数组大幅提升效率
更多推荐
8
0- 0
已为社区贡献2条内容
所有评论(0)