Python 算法详解：冒泡排序（Bubble Sort）完整教程

Python 算法 2 小时前 0 1

冒泡排序（Bubble Sort）是最基础、最经典的排序算法之一，也是初学者学习算法的入门首选。本文将详细讲解冒泡排序的原理、实现、优化以及实际应用。

一、什么是冒泡排序？

冒泡排序是一种简单的比较排序算法。它的基本思想是：

重复地遍历要排序的数列
一次比较两个元素，如果它们的顺序错误就把它们交换过来
重复上述步骤，直到没有再需要交换的元素为止

为什么叫"冒泡"？因为越小的元素会经由交换慢慢"浮"到数列的顶端，就像水中的气泡一样。

二、算法原理

2.1 基本步骤

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

2.2 图解演示

假设我们要排序数组：[5, 3, 8, 4, 2]

第一轮：

5 3 8 4 2  →  3 5 8 4 2  (5和3交换)
3 5 8 4 2  →  3 5 8 4 2  (5和8不交换)
3 5 8 4 2  →  3 5 4 8 2  (8和4交换)
3 5 4 8 2  →  3 5 4 2 8  (8和2交换)
# 最大值 8 已经"冒泡"到末尾

第二轮：

3 5 4 2 8  →  3 5 4 2 8  (3和5不交换)
3 5 4 2 8  →  3 4 5 2 8  (5和4交换)
3 4 5 2 8  →  3 4 2 5 8  (5和2交换)
# 第二大值 5 已经到位

以此类推，直到整个数组有序。

三、Python 代码实现

3.1 基础版本

def bubble_sort(arr):
    """
    冒泡排序 - 基础版本
    
    参数:
        arr: 待排序的列表
    返回:
        排序后的列表
    """
    n = len(arr)
    
    # 外层循环控制轮数
    for i in range(n - 1):
        # 内层循环进行相邻元素比较和交换
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                # 交换元素
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    return arr

# 测试
if __name__ == "__main__":
    test_data = [5, 3, 8, 4, 2]
    print(f"原始数组：{test_data}")
    sorted_data = bubble_sort(test_data.copy())
    print(f"排序后：{sorted_data}")

输出：

原始数组：[5, 3, 8, 4, 2]
排序后：[2, 3, 4, 5, 8]

3.2 优化版本 1：提前结束

如果某一轮中没有发生任何交换，说明数组已经有序，可以提前结束。

def bubble_sort_optimized_v1(arr):
    """
    冒泡排序 - 优化版本 1：提前结束
    
    如果某一轮没有发生交换，说明已经有序，直接返回
    """
    n = len(arr)
    
    for i in range(n - 1):
        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
        
        # 如果没有交换，说明已经有序
        if not swapped:
            print(f"第 {i + 1} 轮发现已有序，提前结束")
            break
    
    return arr

# 测试近乎有序的数组
test_data = [1, 2, 3, 5, 4]
print(f"原始数组：{test_data}")
sorted_data = bubble_sort_optimized_v1(test_data.copy())
print(f"排序后：{sorted_data}")

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

记录最后一次交换的位置，该位置之后的元素已经有序，下一轮不需要再比较。

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

# 测试
test_data = [64, 34, 25, 12, 22, 11, 90]
print(f"原始数组：{test_data}")
sorted_data = bubble_sort_optimized_v2(test_data.copy())
print(f"排序后：{sorted_data}")

四、完整案例：可视化冒泡过程

def bubble_sort_visual(arr):
    """
    冒泡排序 - 可视化版本
    打印每一轮的排序过程
    """
    n = len(arr)
    print(f"初始数组：{arr}\n")
    
    for i in range(n - 1):
        print(f"第 {i + 1} 轮排序:")
        swapped = False
        
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                print(f"  比较 {arr[j]:2d} 和 {arr[j + 1]:2d} → 交换")
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
            else:
                print(f"  比较 {arr[j]:2d} 和 {arr[j + 1]:2d} → 不交换")
        
        print(f"  本轮结果：{arr}\n")
        
        if not swapped:
            print("  已有序，提前结束\n")
            break
    
    return arr

# 运行可视化
print("=" * 50)
bubble_sort_visual([5, 3, 8, 4, 2])
print("=" * 50)

输出示例：

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

第 1 轮排序:
  比较  5 和  3 → 交换
  比较  5 和  8 → 不交换
  比较  8 和  4 → 交换
  比较  8 和  2 → 交换
  本轮结果：[3, 5, 4, 2, 8]

第 2 轮排序:
  比较  3 和  5 → 不交换
  比较  5 和  4 → 交换
  比较  5 和  2 → 交换
  本轮结果：[3, 4, 2, 5, 8]

第 3 轮排序:
  比较  3 和  4 → 不交换
  比较  4 和  2 → 交换
  本轮结果：[3, 2, 4, 5, 8]

第 4 轮排序:
  比较  3 和  2 → 交换
  本轮结果：[2, 3, 4, 5, 8]

==================================================

五、算法复杂度分析

5.1 时间复杂度

最好情况：O(n) - 数组已经有序，只需遍历一次
平均情况：O(n²) - 随机排列的数组
最坏情况：O(n²) - 数组完全逆序

5.2 空间复杂度

O(1) - 只需要常数个额外变量，是原地排序

5.3 稳定性

稳定排序 - 相等元素的相对位置不会改变

六、实际应用场景

虽然冒泡排序效率不高，但在以下场景仍有价值：

教学用途 - 理解排序算法的基础
小规模数据 - 数据量很小时，简单就是优势
近乎有序的数据 - 优化版本可以快速完成
检测数组是否有序 - 一轮遍历即可判断

七、与其他排序算法对比

# 各种排序算法性能对比（1000 个随机数）
import time
import random

def benchmark_sort(sort_func, arr):
    start = time.time()
    sort_func(arr.copy())
    end = time.time()
    return end - start

# 生成测试数据
test_data = [random.randint(1, 10000) for _ in range(1000)]

# 对比测试
print("冒泡排序：", benchmark_sort(bubble_sort, test_data))
print("Python 内置：", benchmark_sort(sorted, test_data))

典型结果：

冒泡排序：~0.05 秒
Python 内置（Timsort）：~0.0001 秒

可以看出，对于大规模数据，冒泡排序效率远低于内置排序。

八、总结

优点：

✅ 简单易懂，适合初学者
✅ 代码实现简单
✅ 稳定排序
✅ 原地排序，空间复杂度 O(1)

缺点：

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

学习建议：

先理解基础版本的原理
掌握优化技巧（提前结束、记录交换位置）
理解时间复杂度的概念
对比学习其他排序算法（选择排序、插入排序、快速排序等）

算法进阶，从冒泡开始！ 🚀

如果你觉得这篇文章有帮助，欢迎收藏和分享！更多 Python 算法教程，敬请期待～

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