Python 冒泡排序算法详解

什么是冒泡排序？

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。

算法原理

基本思想

1. 比较相邻元素：从第一个元素开始，比较相邻的两个元素
2. 交换元素：如果第一个比第二个大（升序排列），就交换它们
3. 重复过程：对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
4. 减少比较范围：每一轮结束后，最大的元素会"冒泡"到末尾，下一轮不需要比较已排序的元素

算法特点

• 时间复杂度：最坏情况 O(n²)，最好情况 O(n)
• 空间复杂度：O(1)
• 稳定性：稳定排序算法
• 适用场景：小规模数据集，教学演示

可视化演示

🎮 交互式演示

想要亲手体验冒泡排序的工作过程吗？请访问我们的 交互式冒泡排序演示页面，您可以：

• 🎯 输入自定义数组或生成随机数组
• 🎬 观看实时的排序动画
• ⏸️ 暂停、继续或单步执行
• 📊 查看详细的统计信息
• 🎮 调整动画速度

让我们通过一个实际例子来理解冒泡排序的工作过程：

初始数组：[64, 34, 25, 12, 22, 11, 90]

第一轮遍历：
64, 34, 25, 12, 22, 11, 90
↑   ↑
比较 64 和 34，64 > 34，交换

34, 64, 25, 12, 22, 11, 90
    ↑   ↑
比较 64 和 25，64 > 25，交换

34, 25, 64, 12, 22, 11, 90
        ↑   ↑
比较 64 和 12，64 > 12，交换

34, 25, 12, 64, 22, 11, 90
            ↑   ↑
比较 64 和 22，64 > 22，交换

34, 25, 12, 22, 64, 11, 90
                ↑   ↑
比较 64 和 11，64 > 11，交换

34, 25, 12, 22, 11, 64, 90
                    ↑   ↑
比较 64 和 90，64 < 90，不交换

第一轮结束：34, 25, 12, 22, 11, 64, 90
最大元素 90 已经在正确位置

基础实现

简单版本

🔢 基础冒泡排序实现 就绪

▶️ 运行代码 🗑️ 清空输出

def bubble_sort_basic(arr): """ 基础冒泡排序实现 """ n = len(arr) # 遍历所有数组元素 for i in range(n): # 最后 i 个元素已经排好序了 for j in range(0, n - i - 1): # 遍历数组从 0 到 n-i-1 # 交换如果发现元素比下一个元素大 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr # 测试代码 test_array = [64, 34, 25, 12, 22, 11, 90] print("原始数组:", test_array) sorted_array = bubble_sort_basic(test_array.copy()) print("排序后:", sorted_array)

点击"运行代码"查看输出...

优化版本

在基础版本中，即使数组已经排序完成，算法仍会继续执行所有轮次。我们可以添加一个标志来检测是否发生了交换，如果某一轮没有交换，说明数组已经排序完成：

⚡ 优化版冒泡排序（提前终止） 就绪

▶️ 运行代码 🗑️ 清空输出

def bubble_sort_optimized(arr): """ 优化后的冒泡排序（增加提前终止机制） """ n = len(arr) for i in range(n): swapped = False # 用于检测是否发生交换 # 最后 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] swapped = True # 如果没有发生交换，说明数组已经排序完成 if not swapped: print(f"在第 {i + 1} 轮后提前终止") break return arr # 测试已经排序的数组 sorted_test = [1, 2, 3, 4, 5] print("已排序数组:", sorted_test) result = bubble_sort_optimized(sorted_test.copy()) print("结果:", result) print() # 测试逆序数组 reverse_test = [5, 4, 3, 2, 1] print("逆序数组:", reverse_test) result2 = bubble_sort_optimized(reverse_test.copy()) print("结果:", result2)

点击"运行代码"查看输出...

详细演示版本

让我们创建一个能够显示每一步过程的详细版本：

🎨 详细演示版冒泡排序 就绪

▶️ 运行代码 🗑️ 清空输出

def bubble_sort_detailed(arr): """ 详细演示版本的冒泡排序 """ n = len(arr) print(f"开始排序数组: {arr}") print("=" * 50) for i in range(n): print(f"\n第 {i + 1} 轮遍历:") swapped = False for j in range(0, n - i - 1): print(f" 比较 arr[{j}]={arr[j]} 和 arr[{j+1}]={arr[j+1]}") if arr[j] > arr[j + 1]: # 交换元素 arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True print(f" → 交换！当前数组: {arr}") else: print(f" → 不需要交换") print(f"第 {i + 1} 轮结束: {arr}") print(f"已确定位置的元素: {arr[n-i-1:]}") if not swapped: print("没有发生交换，排序完成！") break print("=" * 50) print(f"最终结果: {arr}") return arr # 运行详细演示 demo_array = [5, 2, 8, 1, 9] bubble_sort_detailed(demo_array)

点击"运行代码"查看输出...

性能分析

时间复杂度分析

📊 性能测试 就绪

▶️ 运行代码 🗑️ 清空输出

import random import time def bubble_sort_for_test(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] return arr def performance_test(): """测试不同规模数据的性能""" sizes = [100, 200, 500] print("冒泡排序性能测试") print("-" * 40) print("数组大小\t耗时(秒)") for size in sizes: # 生成随机数组 test_data = [random.randint(1, 1000) for _ in range(size)] # 测量时间 start_time = time.time() bubble_sort_for_test(test_data) end_time = time.time() elapsed_time = end_time - start_time print(f"{size}\t\t{elapsed_time:.6f}") # 运行性能测试 performance_test()

点击"运行代码"查看输出...

最好、最坏和平均情况分析

🔍 复杂度分析 就绪

▶️ 运行代码 🗑️ 清空输出

import random def count_operations(arr): """计算比较和交换的次数""" n = len(arr) comparisons = 0 swaps = 0 for i in range(n): for j in range(0, n - i - 1): comparisons += 1 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swaps += 1 return comparisons, swaps def analyze_complexity(): """分析冒泡排序的复杂度""" # 最好情况：已排序数组 best_case = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] comp_best, swap_best = count_operations(best_case.copy()) # 最坏情况：逆序数组 worst_case = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] comp_worst, swap_worst = count_operations(worst_case.copy()) # 平均情况：随机数组 random.seed(42) average_case = [random.randint(1, 10) for _ in range(10)] comp_avg, swap_avg = count_operations(average_case.copy()) print("冒泡排序复杂度分析（数组大小=10）") print("=" * 50) print("情况\t\t比较次数\t交换次数") print(f"最好情况\t{comp_best}\t\t{swap_best}") print(f"最坏情况\t{comp_worst}\t\t{swap_worst}") print(f"平均情况\t{comp_avg}\t\t{swap_avg}") print("\n理论分析:") print("最好情况: O(n²) - 即使已排序也要比较") print("最坏情况: O(n²) - 需要最多交换") print("平均情况: O(n²) - 统计平均性能") analyze_complexity()

点击"运行代码"查看输出...

变体和改进

双向冒泡排序（鸡尾酒排序）

鸡尾酒排序是冒泡排序的一种变体，它在每一轮中同时从两个方向进行冒泡：

🍸 鸡尾酒排序（双向冒泡） 就绪

▶️ 运行代码 🗑️ 清空输出

def cocktail_sort(arr): """ 双向冒泡排序（鸡尾酒排序） """ n = len(arr) start = 0 end = n - 1 swapped = True round_num = 1 print(f"开始鸡尾酒排序: {arr}") print("=" * 40) while swapped: swapped = False print(f"\n第 {round_num} 轮 - 从左到右:") # 从左到右冒泡 for i in range(start, end): print(f" 比较 {arr[i]} 和 {arr[i + 1]}") if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True print(f" → 交换！当前: {arr}") if not swapped: break end -= 1 swapped = False print(f"\n第 {round_num} 轮 - 从右到左:") # 从右到左冒泡 for i in range(end - 1, start - 1, -1): print(f" 比较 {arr[i]} 和 {arr[i + 1]}") if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] swapped = True print(f" → 交换！当前: {arr}") start += 1 round_num += 1 print(f"第 {round_num - 1} 轮结束: {arr}") print("=" * 40) print(f"鸡尾酒排序完成: {arr}") return arr # 测试鸡尾酒排序 cocktail_test = [5, 1, 4, 2, 8, 0, 2] cocktail_sort(cocktail_test)

点击"运行代码"查看输出...

实践练习

练习1：计数器版本

尝试实现一个带计数器的冒泡排序，统计比较和交换的次数：

📝 练习：带计数器的冒泡排序 就绪

▶️ 运行代码 🗑️ 清空输出

def bubble_sort_with_counter(arr): """ 带计数器的冒泡排序，统计比较和交换次数 任务：完善这个函数，添加计数器统计 """ n = len(arr) comparisons = 0 swaps = 0 # TODO: 在这里实现冒泡排序并统计次数 for i in range(n): for j in range(0, n - i - 1): comparisons += 1 # 每次比较计数 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swaps += 1 # 每次交换计数 return arr, comparisons, swaps # 测试用例 test_data = [3, 1, 4, 1, 5, 9, 2, 6] print(f"原始数组: {test_data}") result, comparisons, swaps = bubble_sort_with_counter(test_data.copy()) print(f"排序结果: {result}") print(f"比较次数: {comparisons}") print(f"交换次数: {swaps}") # 计算理论值 n = len(test_data) theoretical_comparisons = n * (n - 1) // 2 print(f"理论最大比较次数: {theoretical_comparisons}") print(f"理论最大交换次数: {theoretical_comparisons}")

点击"运行代码"查看输出...

练习2：自定义比较函数

实现一个支持自定义比较逻辑的冒泡排序：

🎯 练习：自定义比较函数 就绪

▶️ 运行代码 🗑️ 清空输出

def bubble_sort_custom(arr, compare_func=None): """ 支持自定义比较函数的冒泡排序 参数: arr: 要排序的数组 compare_func: 比较函数，返回True表示需要交换 """ if compare_func is None: compare_func = lambda x, y: x > y # 默认升序 n = len(arr) for i in range(n): swapped = False for j in range(0, n - i - 1): if compare_func(arr[j], arr[j + 1]): arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: break return arr # 测试用例1：按长度排序字符串 words = ["apple", "pie", "banana", "book", "a"] print("字符串数组:", words) result1 = bubble_sort_custom(words.copy(), lambda x, y: len(x) > len(y)) print("按长度排序:", result1) # 测试用例2：降序排序数字 numbers = [3, 1, 4, 1, 5, 9, 2, 6] print("\n数字数组:", numbers) result2 = bubble_sort_custom(numbers.copy(), lambda x, y: x < y) print("降序排序:", result2) # 测试用例3：按绝对值排序 mixed = [-5, 3, -1, 7, -2, 4] print("\n混合数组:", mixed) result3 = bubble_sort_custom(mixed.copy(), lambda x, y: abs(x) > abs(y)) print("按绝对值排序:", result3)

点击"运行代码"查看输出...

总结

冒泡排序的优缺点

优点： - 算法简单，容易理解和实现 - 不需要额外的存储空间（原地排序） - 稳定排序算法 - 能够检测数组是否已经排序

缺点： - 时间复杂度较高：O(n²) - 不适合大规模数据排序 - 实际性能较差

适用场景

1. 教学目的：理解排序算法的基本概念
2. 小规模数据：元素数量很少的情况
3. 几乎已排序的数据：优化版本在这种情况下表现较好
4. 稳定性要求：需要保持相等元素的相对顺序

与其他排序算法的比较

算法	时间复杂度(平均)	时间复杂度(最坏)	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定

学习建议

虽然冒泡排序在实际应用中效率不高，但它是理解排序算法的绝佳起点。通过学习冒泡排序，你可以：

• 掌握排序算法的基本思想
• 理解时间复杂度和空间复杂度的概念
• 学会算法的优化思路
• 为学习更复杂的排序算法打下基础

练习建议

1. 尝试手动跟踪算法执行过程
2. 实现本页面的练习题目
3. 比较不同数据规模下的性能
4. 尝试实现其他排序算法并进行比较

继续学习其他排序算法，如快速排序、归并排序等，以获得更全面的算法知识！