题目
冒泡排序算法的实现与优化
信息
- 类型：问答
- 难度：⭐
考点
冒泡排序原理,基础算法实现,时间复杂度分析
快速回答
冒泡排序是一种基础的交换排序算法，通过重复比较相邻元素并交换位置来实现排序。核心要点：
- 每次遍历将最大元素“冒泡”到数组末尾
- 需要两层循环：外层控制遍历轮次，内层执行比较交换
- 时间复杂度为 O(n²)，空间复杂度 O(1)
- 可通过标志位优化减少不必要的比较
原理说明
冒泡排序重复遍历数组，比较相邻元素，如果顺序错误（前大后小）就交换它们。每轮遍历会将当前未排序部分的最大元素移动到正确位置（像气泡上浮）。
代码示例
def bubble_sort(arr):
n = len(arr)
# 优化标志位
swapped = True
# 外层循环控制遍历轮次
for i in range(n-1):
if not swapped:
break # 提前终止
swapped = False
# 内层循环执行比较交换
for j in range(n-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j] # 交换
swapped = True
return arr
# 测试
print(bubble_sort([64, 34, 25, 12, 22, 11, 90])) # 输出 [11, 12, 22, 25, 34, 64, 90]最佳实践
- 优化技巧：添加 swapped 标志位，当某轮无交换时提前终止
- 适用场景：小规模数据或基本有序数据
- 边界处理：内层循环上限为 n-1-i（每轮减少比较范围）
常见错误
- 内层循环使用完整长度（未减去已排序部分）导致冗余比较
- 忘记设置交换标志位，失去优化机会
- 错误比较条件（如写错不等号方向导致降序）
时间复杂度分析
- 最坏情况：完全逆序数组，时间复杂度 O(n²)
- 最好情况：已排序数组（优化后），时间复杂度 O(n)
- 空间复杂度：O(1)（原地排序）
扩展知识
- 稳定性：冒泡排序是稳定排序（相等元素不交换）
- 对比其他排序：比选择排序多交换操作，但优于最坏情况的快速排序
- 实际应用：嵌入式系统等资源受限环境，或作为教学示例
