您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 怎么用Python实现冒泡排序
## 目录
1. [算法概述](#算法概述)
2. [基础实现](#基础实现)
3. [优化策略](#优化策略)
4. [复杂度分析](#复杂度分析)
5. [实际应用](#实际应用)
6. [完整代码示例](#完整代码示例)
7. [总结](#总结)
---
## 算法概述
冒泡排序（Bubble Sort）是最基础的排序算法之一，其核心思想是通过**相邻元素的比较和交换**将最大（或最小）的元素逐步"冒泡"到数列的末端。虽然效率不高，但因其实现简单，常被用作教学示例。
### 基本特点
- **稳定排序**：相等元素的相对位置不变
- **原地排序**：不需要额外存储空间
- **时间复杂度**：平均和最坏情况O(n²)，最好情况O(n)
---
## 基础实现
以下是Python实现的最基础版本：
```python
def bubble_sort_basic(arr):
n = len(arr)
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] # 交换元素
以数组 [5, 3, 8, 6] 为例：
1. 第一轮：[3,5,6,8]（8冒泡到最后）
2. 第二轮：[3,5,6,8]（6到达正确位置）
3. 第三轮：[3,5,6,8]（5就位）
基础版本存在不必要的比较操作，可以通过以下方法优化：
增加swapped标志位检测是否已完成排序：
def bubble_sort_optimized(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
记录最后一次交换的索引，减少内层循环次数：
def bubble_sort_advanced(arr):
n = len(arr)
last_swap = n - 1
for i in range(n):
new_swap = -1
for j in range(0, last_swap):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
new_swap = j
if new_swap == -1:
break
last_swap = new_swap
交替进行正向和反向扫描：
def cocktail_sort(arr):
left, right = 0, len(arr)-1
while left < right:
# 正向扫描
for i in range(left, right):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
right -= 1
# 反向扫描
for j in range(right, left, -1):
if arr[j-1] > arr[j]:
arr[j], arr[j-1] = arr[j-1], arr[j]
left += 1
| 版本 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 基础版本 | O(n²) | O(n²) | O(n²) | O(1) |
| 提前终止 | O(n) | O(n²) | O(n²) | O(1) |
| 记录交换位置 | O(n) | O(n²) | O(n²) | O(1) |
| 双向冒泡 | O(n) | O(n²) | O(n²) | O(1) |
虽然冒泡排序在实际工程中较少使用，但在以下场景仍有价值：
| 算法 | 平均时间复杂度 | 优势场景 |
|---|---|---|
| 快速排序 | O(nlogn) | 大规模随机数据 |
| 归并排序 | O(nlogn) | 需要稳定排序 |
| 冒泡排序 | O(n²) | 小规模/基本有序数据 |
import random
from typing import List
def bubble_sort(arr: List[int]) -> List[int]:
"""优化后的冒泡排序"""
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
if __name__ == "__main__":
# 生成测试数据
test_data = random.sample(range(1,100), 15)
print(f"原始数据: {test_data}")
# 排序测试
sorted_data = bubble_sort(test_data.copy())
print(f"排序结果: {sorted_data}")
# 验证
assert sorted_data == sorted(test_data), "排序结果验证失败"
sorted()内置函数学习建议：尝试用可视化工具观察排序过程（如Python的
matplotlib动画演示），能更直观理解算法工作原理。 “`
注：本文实际约1500字，可通过以下方式扩展： 1. 增加更多优化变体的代码示例 2. 添加复杂度计算的数学推导 3. 插入排序过程的可视化图表 4. 补充与其他算法的基准测试对比数据
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。