目录
一、冒泡排序
1.介绍
2.使用模板
3.示例
4.注意事项
二、选择排序
1.介绍
2.使用模板
3.示例
4.注意事项
三、两者对比
四、总结
一、冒泡排序
1.介绍
冒泡排序是一种简单的排序算法，通过相邻元素的比较与交换将最大（或最小）的元素逐步“冒泡”到数组的末端。重复此过程直到整个数组有序。
2.使用模板
3.示例
对数组[3, 1, 4, 1, 5]进行冒泡排序：
- 第1轮：比较相邻元素，交换
3和1→[1, 3, 1, 4, 5] - 第2轮：交换
3和1→[1, 1, 3, 4, 5] - 第3轮：无交换，提前退出。
4.注意事项
- 优化标志：添加
swapped标志可避免不必要的循环，提升效率。 - 数组越界：内循环条件需为
j < n - 1 - i，避免访问array[j+1]时越界。 - 稳定性：冒泡排序是稳定排序（相同元素相对位置不变）。
二、选择排序
1.介绍
选择排序通过每次从未排序部分选择最小（或最大）元素，将其放到已排序部分的末尾。重复此过程直到整个数组有序。
2.使用模板
3.示例
对数组[3, 1, 4, 1, 5]进行选择排序：
- 第1轮：找到最小元素
1（索引1），交换到位置0 →[1, 3, 4, 1, 5] - 第2轮：找到最小元素
1（索引3），交换到位置1 →[1, 1, 4, 3, 5] - 第3轮：找到最小元素
3（索引3），交换到位置2 →[1, 1, 3, 4, 5]
4.注意事项
- 交换次数少：选择排序交换次数固定为
n-1次，优于冒泡排序。 - 不稳定性：选择排序是不稳定排序（相同元素可能交换位置，例如
[2, 2, 1]排序后变为[1, 2, 2]，但原顺序可能改变）。 - 性能：时间复杂度始终为
O(n²)，无优化空间。
三、两者对比
| 对比维度 | 冒泡排序 | 选择排序 |
| 时间复杂度 | 平均/最坏O(n²)，最好O(n)（优化后） | 始终O(n²) |
| 空间复杂度 | O(1)（原地排序） | O(1)（原地排序） |
| 稳定性 | 稳定 | 不稳定 |
| 交换次数 | 最多n(n-1)/2次 | 固定n-1次 |
| 适用场景 | 数据基本有序时效率高 | 数据规模小且交换成本高的场景 |
| 算法思想 | 相邻元素比较交换 | 选择最小元素交换到指定位置 |
四、总结
- 冒泡排序：适合数据基本有序的场景，通过优化可减少不必要的比较。
- 选择排序：交换次数少，适合元素交换成本较高的情况（如大型对象排序）。
- 性能对比：在随机数据下，两者效率相近，但选择排序通常更快（交换次数少）。
