Python 算法教程（1）：冒泡排序详解

Python 算法 3 周前 0 6

前言

冒泡排序（Bubble Sort）是最基础的排序算法之一，也是学习算法的入门第一课。虽然在实际生产中很少使用，但理解冒泡排序有助于掌握排序算法的核心思想。

一、算法原理

1.1 核心思想

冒泡排序的核心思想非常简单：

比较相邻的两个元素，如果前一个比后一个大，就交换它们
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对
这步做完后，最后的元素会是最大的数（已经"冒泡"到顶部）
针对所有的元素重复以上的步骤，除了最后一个
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

1.2 动画演示

初始数组：[5, 3, 8, 4, 2]

第一轮（找到最大值 8）：
[5, 3, 8, 4, 2]  → 比较 5 和 3，交换
[3, 5, 8, 4, 2]  → 比较 5 和 8，不交换
[3, 5, 8, 4, 2]  → 比较 8 和 4，交换
[3, 5, 4, 8, 2]  → 比较 8 和 2，交换
[3, 5, 4, 2, 8]  ✓ 8 已就位

第二轮（找到次大值 5）：
[3, 5, 4, 2, 8]  → 比较 3 和 5，不交换
[3, 5, 4, 2, 8]  → 比较 5 和 4，交换
[3, 4, 5, 2, 8]  → 比较 5 和 2，交换
[3, 4, 2, 5, 8]  ✓ 5 已就位

第三轮（找到 4）：
[3, 4, 2, 5, 8]  → 比较 3 和 4，不交换
[3, 4, 2, 5, 8]  → 比较 4 和 2，交换
[3, 2, 4, 5, 8]  ✓ 4 已就位

第四轮（找到 3）：
[3, 2, 4, 5, 8]  → 比较 3 和 2，交换
[2, 3, 4, 5, 8]  ✓ 3 已就位

最终结果：[2, 3, 4, 5, 8]

二、代码实现

2.1 基础版本

def bubble_sort_basic(arr):
    """
    冒泡排序 - 基础版本
    时间复杂度：O(n²)，空间复杂度：O(1)
    """
    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

# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_basic(arr))  # 输出：[11, 12, 22, 25, 34, 64, 90]

2.2 优化版本 1：提前终止

def bubble_sort_optimized(arr):
    """
    冒泡排序 - 优化版本 1（提前终止）
    如果某一趟没有发生交换，说明已经有序，可以提前结束
    最好情况时间复杂度：O(n)
    """
    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

# 测试 - 已经有序的数组
arr = [1, 2, 3, 4, 5]
print(bubble_sort_optimized(arr))  # 输出：[1, 2, 3, 4, 5]，只需一趟

2.3 优化版本 2：记录最后交换位置

def bubble_sort_optimized_v2(arr):
    """
    冒泡排序 - 优化版本 2（记录最后交换位置）
    记录最后一次交换的位置，该位置之后的元素已经有序
    """
    n = len(arr)
    
    while n > 0:
        last_swap = 0  # 记录最后一次交换的位置
        
        for j in range(1, n):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
                last_swap = j
        
        n = last_swap  # 更新边界
    
    return arr

# 测试
arr = [5, 3, 8, 4, 2]
print(bubble_sort_optimized_v2(arr))  # 输出：[2, 3, 4, 5, 8]

2.4 可视化版本（打印每轮结果）

def bubble_sort_visual(arr):
    """
    冒泡排序 - 可视化版本
    打印每一轮的排序过程
    """
    n = len(arr)
    print(f"初始数组：{arr}\n")
    
    for i in range(n):
        print(f"第 {i + 1} 轮:")
        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
        
        print(f"  结果：{arr}")
        
        if not swapped:
            print("  已有序，提前终止\n")
            break
        print()
    
    return arr

# 测试
bubble_sort_visual([5, 3, 8, 4, 2])

三、复杂度分析

3.1 时间复杂度

情况	时间复杂度	说明
最好情况	O(n)	数组已经有序，只需一趟比较
平均情况	O(n²)	随机数组
最坏情况	O(n²)	数组完全逆序

详细分析：

比较次数：(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ O(n²)
交换次数：最好 0 次，最坏 n(n-1)/2 次

3.2 空间复杂度

空间复杂度：O(1) - 原地排序，只需要常数级别的额外空间
稳定性：稳定 - 相等元素的相对位置不会改变

四、算法特点

4.1 优点

✅ 实现简单，易于理解
✅ 空间复杂度 O(1)，不需要额外空间
✅ 稳定排序
✅ 可以检测数组是否已经有序（优化版本）

4.2 缺点

❌ 时间复杂度 O(n²)，效率低
❌ 需要多次遍历数组
❌ 不适合大规模数据排序

五、实际应用

5.1 适用场景

教学演示 - 学习排序算法的入门案例
小规模数据 - 数据量 n < 50 时可以考虑
几乎有序的数据 - 优化版本可以达到 O(n)
稳定性要求 - 需要保持相等元素相对位置

5.2 不适用场景

大规模数据排序（使用快速排序、归并排序）
对性能要求高的场景
实时系统

六、与其他排序算法对比

排序算法对比（n=1000 的随机数组）：

冒泡排序：    ~500,000 次比较
选择排序：    ~500,000 次比较
插入排序：    ~250,000 次比较
快速排序：    ~10,000 次比较
归并排序：    ~10,000 次比较

结论：冒泡排序在实际应用中效率最低

七、完整测试代码

def 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

# 测试用例
def test_bubble_sort():
    # 测试 1：普通数组
    arr1 = [64, 34, 25, 12, 22, 11, 90]
    assert bubble_sort(arr1.copy()) == sorted(arr1)
    
    # 测试 2：已经有序
    arr2 = [1, 2, 3, 4, 5]
    assert bubble_sort(arr2.copy()) == sorted(arr2)
    
    # 测试 3：完全逆序
    arr3 = [5, 4, 3, 2, 1]
    assert bubble_sort(arr3.copy()) == sorted(arr3)
    
    # 测试 4：有重复元素
    arr4 = [3, 1, 4, 1, 5, 9, 2, 6]
    assert bubble_sort(arr4.copy()) == sorted(arr4)
    
    # 测试 5：空数组
    arr5 = []
    assert bubble_sort(arr5.copy()) == sorted(arr5)
    
    # 测试 6：单元素
    arr6 = [1]
    assert bubble_sort(arr6.copy()) == sorted(arr6)
    
    print("所有测试通过！✓")

test_bubble_sort()

八、学习建议

理解原理 - 先手动模拟几轮排序过程
手写代码 - 不看答案独立实现基础版本
理解优化 - 思考如何减少不必要的比较
对比学习 - 学完冒泡排序后，继续学习选择排序、插入排序

总结

冒泡排序作为排序算法的入门，虽然在实际应用中效率不高，但学习价值很大：

✓ 理解排序的基本思想
✓ 掌握嵌套循环的使用
✓ 学习算法优化的思路
✓ 为学习更高级的排序算法打基础

下一篇预告： 选择排序 - 另一种简单直观的排序算法，比较次数固定为 O(n²)，但交换次数更少。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

前言