Algorithm-bubbleSort 标准冒泡排序

type

status

date

slug

summary

一、冒泡排序的核心思想

通过 相邻元素的比较和交换，每一轮将 未排序部分的最大值“冒泡”到正确位置。

经过 n-1 轮（n 为数组长度）后，所有元素有序。

二、标准实现步骤

1. 初始化外层循环

循环次数：n-1 次（n 是数组长度）

因为 n 个元素最多需要 n-1 轮比较即可完成排序。 • 循环变量：i（从 0 开始，到 n-2 结束）

2. 内层循环控制比较范围

每轮比较次数：n-1-i

因为每轮结束后，末尾的 i 个元素已排序，无需再比较。 • 循环变量：j（从 0 开始，到 n-2-i 结束）

三、示例演示

以数组 {5, 3, 8, 6, 2} 为例，逐步展示排序过程：

初始数组：

第一轮外层循环 (`i=0`):

比较范围：索引 0 到 3（共 4 次比较）

比较 5 和 3 → 交换 → [3, 5, 8, 6, 2]

比较 5 和 8 → 不交换

比较 8 和 6 → 交换 → [3, 5, 6, 8, 2]

比较 8 和 2 → 交换 → [3, 5, 6, 2, 8]结果：最大值 8 已就位。

第二轮外层循环 (`i=1`):

比较范围：索引 0 到 2（共 3 次比较）

比较 3 和 5 → 不交换

比较 5 和 6 → 不交换

比较 6 和 2 → 交换 → [3, 5, 2, 6, 8]结果：6 就位。

第三轮外层循环 (`i=2`):

比较范围：索引 0 到 1（共 2 次比较）

比较 3 和 5 → 不交换

比较 5 和 2 → 交换 → [3, 2, 5, 6, 8]结果：5 就位。

第四轮外层循环 (`i=3`):

比较范围：索引 0（共 1 次比较）

比较 3 和 2 → 交换 → [2, 3, 5, 6, 8]结果：3 就位，排序完成。

四、代码实现（含优化）

五、关键点解析

1. 外层循环次数

只需 n-1 轮：因为每轮至少确定一个最大值的位置，最后剩下的元素无需比较。

2. 内层循环的边界

j < array.length - 1 - i：确保 j+1 不越界，且跳过已排序部分。

3. 优化策略

提前终止：如果某轮未发生交换，说明数组已有序，可提前结束排序。

4. 时间复杂度

场景	时间复杂度	说明
最坏情况	O(n²)	数组完全逆序
最好情况	O(n)	数组已有序（通过优化）
平均情况	O(n²)	一般随机数组

六、常见问题

1. 为什么外层循环是 `n-1` 次？

如果数组有 n 个元素，最多需要 n-1 轮即可确保所有元素有序（最后一轮只剩一个元素，无需比较）。

2. 如何避免越界？

内层循环条件 j < array.length - 1 - i 确保 j+1 始终有效。

3. 是否支持自定义排序顺序？

是的，只需修改比较逻辑：

七、总结

冒泡排序通过 逐步交换相邻元素 将最大值“冒泡”到右侧，其标准实现需注意：

循环边界：外层 n-1 次，内层逐步缩小范围。

越界防护：内层循环条件确保 j+1 有效。

性能优化：通过标志位提前终止无意义的循环。