冒泡排序（Bubble Sort）
冒泡排序每一轮只解决一件事：把当前未排序区间里的最大值“顶”到末尾。
定义
冒泡排序是一种简单的排序算法，通过重复遍历待排序序列，比较相邻元素并交换位置，使较大（或较小）的元素逐步”冒泡”到序列末端。
核心思路
- 比较相邻的元素，如果顺序错误就交换
- 每轮遍历后，最大（或最小）的元素会移动到末尾
- 重复以上步骤，直到整个序列有序
第一轮冒泡：[5,3,8,6,2] → [3,5,6,2,8] (8冒泡到末尾)
第二轮冒泡：[3,5,6,2,8] → [3,5,2,6,8] (6冒泡到倒数第二)
第三轮冒泡：[3,5,2,6,8] → [3,2,5,6,8] (5到位)
第四轮冒泡：[3,2,5,6,8] → [2,3,5,6,8] (完成)
为什么叫“冒泡”
因为大元素会通过一轮轮相邻交换，像气泡一样慢慢浮到右侧末尾。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 最好时间 | O(n) | 已排序，只需一轮遍历 |
| 平均时间 | O(n²) | 需要n轮，每轮平均n/2次比较 |
| 最坏时间 | O(n²) | 逆序排列 |
| 空间复杂度 | O(1) | 原地排序 |
| 稳定性 | ✅ 稳定 | 相等元素不交换 |
Go 代码
Go 实现
package main
import "fmt"
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
swapped := false
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
}
}
// 优化：没有交换则提前结束
if !swapped {
break
}
}
}
func main() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("原始数组:", arr)
bubbleSort(arr)
fmt.Println("排序后:", arr)
}易错点
冒泡排序很简单，但也最容易把循环边界写得又慢又乱。
- 第
i轮结束后，最后i个位置已经有序。 - 内层循环上界应当随着轮次缩短。
swapped优化不能忘，否则几乎有序数组也会白跑很多轮。
算法优化
经典题目
基础应用
变体题目
- 统计冒泡排序的交换次数
- 使用冒泡排序找第k大元素
- 局部有序数组排序
优缺点
优点
- ✅ 实现简单，易于理解
- ✅ 稳定排序
- ✅ 原地排序（O(1)空间）
- ✅ 适合小数据量
缺点
- ❌ 时间复杂度高 O(n²)
- ❌ 大数据量性能差
- ❌ 比较和交换次数多
- ❌ 实际应用较少
应用场景
- 教学演示：算法入门的经典案例
- 小数据集：数据量很小（<10个元素）
- 几乎有序：数据基本有序时，优化后性能可接受
- 稳定性要求：需要稳定排序且数据量小
何时使用冒泡排序
- ✅ 数据量很小（通常 < 10）
- ✅ 数据基本有序
- ✅ 需要稳定排序
- ✅ 代码简洁性比性能更重要
- ❌ 不推荐：大数据量、性能敏感场景