如何用Python实现冒泡排序算法
一、冒泡排序的原理简介
冒泡排序（Bubble Sort）是一种简单的排序算法，其核心思想是通过不断比较相邻元素并交换位置，将较大的元素逐渐“浮”到数组的末尾，就像气泡上浮一样。它的主要特点：
- 时间复杂度：最坏和平均情况为 (O(n^2))
- 空间复杂度：(O(1))（仅需少量临时变量）
- 稳定性：稳定排序（相等元素的相对位置不变）
二、算法步骤分解
以列表 [5, 3, 8, 4, 2] 为例，分步骤说明冒泡排序的执行过程：
步骤1：外层循环控制遍历次数
- 需要遍历 (n-1) 次（(n) 是列表长度）。例如，长度为5的列表需要遍历4次。
步骤2：内层循环进行相邻元素比较与交换
- 每次外层循环后，最大的元素会被“冒泡”到末尾，因此内层循环的范围可以逐渐缩小。
- 比较规则：若前一个元素 > 后一个元素，则交换它们的位置。
步骤3：优化（可选）
- 如果某次遍历中没有发生交换，说明列表已有序，可提前终止排序。
三、Python代码实现
3.1 基础版本（无优化）
def bubble_sort(lst):
n = len(lst)
for i in range(n-1): # 外层循环：控制遍历次数
for j in range(n-1-i): # 内层循环：比较相邻元素
if lst[j] > lst[j+1]:
# 交换元素（Python元组交换）
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst
# 测试
test_list = [64, 34, 25, 12, 22, 11, 90]
print("原始列表：", test_list)
bubble_sort(test_list)
print("排序后：", test_list)
3.2 代码解释
- 外层循环：for i in range(n-1)
- 每次循环处理一层，例如第一次处理后最大的元素会到末尾，第二次处理次大的元素到倒数第二位，以此类推。
- 内层循环：for j in range(n-1-i)
- 每次内层循环从头开始比较相邻元素，范围随着外层循环递减（因为已处理过的元素已有序）。
- 交换条件：if lst[j] > lst[j+1]
- 如果当前元素比下一个大，则交换位置。
四、优化版本（提前终止）
当某次遍历中没有发生交换时，说明列表已经有序，可以提前结束排序。修改代码如下：
def bubble_sort_optimized(lst):
n = len(lst)
for i in range(n-1):
swapped = False # 标记是否发生交换
for j in range(n-1-i):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
swapped = True # 发生交换
if not swapped:
break # 无交换，提前终止
return lst
五、测试与验证
5.1 正常测试
test_list = [64, 34, 25, 12, 22, 11, 90]
print("原始列表：", test_list)
bubble_sort(test_list)
print("排序后：", test_list) # 输出：[11, 12, 22, 25, 34, 64, 90]
5.2 边界测试
- 空列表：bubble_sort([]) → 返回 []
- 单元素列表：bubble_sort([5]) → 返回 [5]
- 已排序列表：bubble_sort([1,2,3,4]) → 仍会遍历但无交换（优化版更快终止）
六、总结步骤
- 理解冒泡排序原理：通过相邻元素的比较和交换，逐步将元素“冒泡”到正确位置。
- 编写外层循环：控制遍历次数（(n-1) 次）。
- 编写内层循环：遍历未排序部分，执行比较与交换。
- 添加优化（可选）：通过 swapped 标记提前终止。
- 测试与调试：用不同测试用例验证代码。
七、练习题
- 将代码中的 > 改为 <，实现降序排序。
- 尝试用临时变量实现元素交换（替代元组交换）：temp = lst[j] lst[j] = lst[j+1] lst[j+1] = temp
- 计算原始版本和优化版本的时间差异（可使用 time 模块）。
通过以上步骤，可以逐步掌握冒泡排序的实现方法，并理解其核心逻辑。