冒泡排序
定义
冒泡排序是一种简单的交换排序算法，通过重复遍历数组，比较相邻元素并交换逆序对，使较大（或较小）的元素像气泡一样逐渐"浮"到数组末端。
算法原理
- 从第一个元素开始，依次比较相邻两个元素
- 如果顺序错误（逆序），则交换它们
- 一轮遍历后，最大（或最小）元素会"冒泡"到末尾
- 重复上述过程，每轮减少一个元素的比较范围
- 直到没有任何交换发生，排序完成
核心特性
| 特性 |
说明 |
| 时间复杂度 |
最坏/平均 O(n²)，最好 O(n)（已排序） |
| 空间复杂度 |
O(1)（原地排序） |
| 稳定性 |
稳定（相等元素保持原有相对顺序） |
| 适用场景 |
小规模数据或教学演示 |
优化版本
1. 稳定性优化（从选择排序演进）
- 选择排序是不稳定的，因为它会跨多个位置交换
- 冒泡排序只交换相邻元素，天然稳定
2. 提前终止机制
- 如果某轮遍历没有发生任何交换，说明数组已经有序，可以提前结束
- 最好情况下（已排序数组）时间复杂度可达 O(n)
3. 记录最后交换位置
与选择排序对比
| 维度 |
冒泡排序 |
选择排序 |
| 稳定性 |
稳定 |
不稳定 |
| 交换次数 |
较多（每次逆序都交换） |
较少（每轮只交换一次） |
| 最好情况 |
O(n)（提前终止） |
O(n²)（无法利用有序性） |
| 适用场景 |
需要稳定排序的小规模数据 |
不关心稳定性，追求交换次数少 |
与插入排序对比
| 维度 |
冒泡排序 |
插入排序 |
| 核心思想 |
不断交换相邻逆序对 |
将元素插入左侧有序数组 |
| 最好情况 |
O(n) |
O(n) |
| 实际性能 |
通常较慢（交换开销大） |
通常更快（移动操作比交换开销小） |
| 稳定性 |
稳定 |
稳定 |
相关概念
- 排序算法：冒泡排序是经典排序算法之一
- 选择排序：另一种简单排序，但不稳定
- 插入排序：同为 O(n²) 稳定排序，实际性能更优
- 稳定排序：冒泡排序是稳定排序的典型例子