上一篇
Python冒泡排序算法详解 - 从原理到实现完整教程
Python冒泡排序算法详解
从原理到实现 - 完整教程
冒泡排序简介
冒泡排序（Bubble Sort）是最简单的排序算法之一，因其工作方式像水中的气泡逐渐上浮而得名。
核心思想：重复遍历要排序的列表，比较相邻的两个元素，如果顺序错误就交换它们。遍历列表的工作会重复进行，直到列表已经排序完成。
特点：
- 简单易懂，适合教学和初学者
- 空间复杂度低（O(1)）
- 稳定排序（相等元素的相对位置不变）
5
1
8
3
未排序的数组示例
算法原理
冒泡排序的基本操作是通过多次遍历数组实现的：
- 从数组的第一个元素开始，比较相邻的两个元素
- 如果第一个元素比第二个大（升序排序），则交换它们的位置
- 移动到下一对相邻元素，重复上述比较和交换操作
- 当遍历完整个数组后，最大的元素会"冒泡"到数组末尾
- 重复上述步骤，每次遍历忽略最后一个已排序的元素
- 当一次遍历中没有发生任何交换时，排序完成
排序过程示例
初始数组
5
1
8
3
第一次遍历
1
5
3
8
第二次遍历
1
3
5
8
第三次遍历
1
3
5
8
绿色边框表示已排序到正确位置的元素
Python实现
下面是冒泡排序算法的基本Python实现：
def bubble_sort(arr):
"""
冒泡排序算法实现
参数:
arr -- 待排序的列表
返回:
排序后的列表
"""
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# 最后i个元素已经排好序，不需要再比较
for j in range(0, n-i-1):
# 如果当前元素大于下一个元素，则交换
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 测试冒泡排序
if __name__ == "__main__":
sample_array = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", sample_array)
sorted_array = bubble_sort(sample_array)
print("排序后:", sorted_array)
代码解析
- 外层循环 (for i in range(n)): 控制排序的轮数
- 内层循环 (for j in range(0, n-i-1)): 执行相邻元素的比较和交换操作
- 比较操作 (if arr[j] > arr[j+1]): 比较相邻的两个元素
- 交换操作 (arr[j], arr[j+1] = arr[j+1], arr[j]): Python特有的交换方式，不需要临时变量
- n-i-1: 每轮排序后，最大的元素会移动到末尾，因此后续轮次可以减少比较次数
可视化示例
下面的可视化展示了冒泡排序的工作过程：
点击"开始排序"按钮查看冒泡排序过程
优化技巧
基本冒泡排序算法可以通过以下方法进行优化：
1. 提前终止优化
当某次遍历中没有发生任何交换时，说明数组已经有序，可以提前终止排序。
def optimized_bubble_sort(arr):
n = len(arr)
for i in range(n):
# 添加交换标志
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
# 如果没有发生交换，提前结束
if not swapped:
break
return arr
2. 记录最后交换位置
记录最后一次交换的位置，该位置之后的元素已经有序，下次遍历只需比较到该位置。
def further_optimized_bubble_sort(arr):
n = len(arr)
last_swap = n - 1
for i in range(n):
# 设置当前遍历的结束位置
current_end = last_swap
new_last_swap = 0
for j in range(0, current_end):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
new_last_swap = j # 记录最后一次交换的位置
last_swap = new_last_swap
# 如果最后一次交换位置为0，说明数组已排序完成
if last_swap == 0:
break
return arr
优化效果对比
| 算法版本 | 最好情况 | 最坏情况 | 平均情况 | 空间复杂度 |
|---|---|---|---|---|
| 基本冒泡排序 | O(n²) | O(n²) | O(n²) | O(1) |
| 优化版本1 | O(n) | O(n²) | O(n²) | O(1) |
| 优化版本2 | O(n) | O(n²) | O(n²) | O(1) |
时间复杂度分析
最坏情况
当数组完全逆序时，需要执行完整的n(n-1)/2次比较和交换操作。
O(n²)
最好情况
当数组已经有序时，优化后的冒泡排序只需遍历一次即可确定。
O(n)
平均情况
随机数组的排序时间复杂度与基本版本相同。
O(n²)
空间复杂度
冒泡排序是原地排序算法，不需要额外的存储空间。
O(1)
实际应用场景
虽然冒泡排序在实际应用中较少使用（因为有效率的替代算法如快速排序、归并排序等），但在某些特定场景下仍有价值：
教学目的
由于其简单性，冒泡排序是算法入门教学的理想选择，有助于理解排序算法的基本原理。
小规模数据集
对于非常小的数据集（n ≤ 10），冒泡排序的性能损失可以忽略不计，代码简单反而更有优势。
几乎有序的数组
当数组已经基本有序时，优化后的冒泡排序可能比其他O(n log n)算法更高效。
使用建议
- 在真实项目中，优先考虑更高效的排序算法（如Python内置的sorted()函数）
- 仅当数据集非常小且简单排序逻辑足够时考虑使用
- 在嵌入式系统等资源受限环境中，冒泡排序可能因简单性而被选用
总结
冒泡排序是理解排序算法基础的绝佳起点。尽管它在实际应用中效率不高，但通过学习和实现冒泡排序，可以深入理解算法设计、时间复杂度和优化策略等核心概念。
继续探索更高效的排序算法，如快速排序、归并排序和堆排序！
本文由LiangZhuo于2025-07-27发表在吾爱品聚，如有疑问，请联系我们。
本文链接：https://www.521pj.cn/20256674.html
发表评论