Python案例如何实现冒泡排序？

wen python案例 2026-06-11 6

Python案例实战：冒泡排序算法从原理到代码优化全解析

一文学会冒泡排序的多种实现方式与时间复杂度分析**

Python案例如何实现冒泡排序？

📑 目录导读

什么是冒泡排序？—— 核心思想与生活类比
Python基础实现：一个简单的冒泡排序案例
代码逐行拆解：图解循环与交换过程
性能优化：如何减少不必要的比较次数？
时间复杂度与空间复杂度深度分析
常见错误与调试技巧（附问答环节）
冒泡排序的变种：双向冒泡与递归实现
实战案例：对用户输入的成绩列表进行排序
与Python内置排序的性能对比
总结与学习建议

❓ 开篇问答

问：为什么学习冒泡排序？Python中有现成的.sort()方法，还需要自己手写排序算法吗？
答：这是一个经典问题，虽然Python内置排序（Timsort算法）效率极高，但理解冒泡排序能帮你透彻掌握三点：

算法思维：循环、条件判断、变量交换等基础编程逻辑的实战训练。
优化意识：从低效到高效，你亲身体验算法优化的过程。
面试考点：冒泡排序是互联网大厂面试考频最高的算法之一，手写代码是基本要求。
扩展基础：理解冒泡后，更容易理解快速排序、堆排序等高级排序。

什么是冒泡排序？—— 核心思想与生活类比

冒泡排序是一种简单直观的排序算法，它的名字来源于“气泡”浮上水面的过程：

依次比较相邻的两个元素，如果顺序错误（例如前一个大于后一个），就交换它们。
每轮遍历后，最大（或最小）的元素会像气泡一样“浮”到数列的末尾。
重复这个过程，直到没有任何元素需要交换,排序完成。

生活类比：
想象一排高低不齐的砖块，你从头开始，每次比较相邻两块，高的往后挪，经过多轮“冒泡”，最高的砖块会移到最右边，次高的移到右边第二位……最终形成从矮到高的序列。

Python基础实现：一个简单的冒泡排序案例

def bubble_sort(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
# 测试案例
sample_list = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", sample_list)
sorted_list = bubble_sort(sample_list.copy())
print("排序后:", sorted_list)

输出结果：

排序前: [64, 34, 25, 12, 22, 11, 90]
排序后: [11, 12, 22, 25, 34, 64, 90]

代码逐行拆解：图解循环与交换过程

外层循环 `for i in range(n-1)`

n是列表长度，若列表有n个元素，则最多只需要n-1轮遍历（最后剩一个元素不用比较）。
每一轮结束后，一个元素归位（最大元素浮动到尾端）。

内层循环 `for j in range(n-1-i)`

每轮比较的次数逐渐减少，因为末尾已排序好的元素无需再比较。
例如第1轮比较n-1次，第2轮比较n-2次……

交换操作 `arr[j], arr[j+1] = arr[j+1], arr[j]`

Python特有的元素交换语法，等价于先存temp，再交换。
条件 if arr[j] > arr[j+1] 决定交换时机（升序排序）。

动态图解（文字模拟）

以列表 [5, 3, 8, 4] 为例：

第一轮：
比较5和3 → 5>3，交换 → [3,5,8,4]
比较5和8 → 5<8，不交换
比较8和4 → 8>4，交换 → [3,5,4,8]  ← 8浮到末尾
第二轮：
比较3和5 → 3<5，不交换
比较5和4 → 5>4，交换 → [3,4,5,8]  ← 5浮到次末尾
第三轮：
比较3和4 → 3<4，不交换 → 排序完成

性能优化：如何减少不必要的比较次数？

优化1：添加标志位（提前终止）

如果某一轮遍历中没有发生任何交换，说明列表已有序,可以提前退出。

def bubble_sort_optimized(arr):
    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:
            break
    return arr

测试极优情况：如果输入[1,2,3,4,5]，只需扫描一轮（比较4次），复杂度降为O(n)。

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

在某一轮中，最后一次交换发生的位置之后的元素都已有序,下一轮只需比较到该位置。

def bubble_sort_last_swap(arr):
    n = len(arr)
    last_swap_index = n - 1
    while last_swap_index > 0:
        new_last_swap = 0
        for j in range(last_swap_index):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                new_last_swap = j  # 记录最后交换的位置
        last_swap_index = new_last_swap
    return arr

时间复杂度与空间复杂度深度分析

指标	数值	说明
最坏时间复杂度	O(n²)	完全逆序数组，每轮都需交换所有相邻元素
最好时间复杂度	O(n)	数组已有序，添加优化标志位后只需一轮遍历
平均时间复杂度	O(n²)	随机数据平均表现
空间复杂度	O(1)	只使用了常数个辅助变量（原地排序）
稳定性	稳定	相等元素不交换，相对顺序保持不变

为什么是O(n²)？
比较次数 = (n-1) + (n-2) + ... + 1 = ( \frac{n(n-1)}{2} )，取最高阶n²。

常见错误与调试技巧（附问答环节）

🚫 错误1：循环范围写错

# 错误写法
for i in range(n):      # 多了一轮
    for j in range(n):  # 每次比较全部元素

修正：外层n-1，内层n-1-i。

🚫 错误2：忘记使用副本

直接修改原列表且不返回副本，可能导致函数副作用。
最佳实践：调用时用arr.copy()传入副本,或函数内部操作副本后返回。

🚫 错误3：比较方向搞反

if arr[j] < arr[j+1]:  # 这会排成降序

❓ 问答环节

Q：为什么冒泡排序在实际项目中很少使用？
A：因为O(n²)的时间复杂度在数据量大时（如10万个元素）效率极低（比较约50亿次），而Python内置的Timsort会用O(n log n)级别完成，冒泡排序主要用于教学和小数据集（如几十个元素）。

Q：冒泡排序可以处理负数或浮点数吗？
A：可以，只要元素之间支持>比较运算符（即类型一致且可比较）。

Q：如果列表中有重复元素，会怎样？
A：稳定排序，重复元素的相对位置不会改变，例如[3a, 3b, 1]排序后为[1, 3a, 3b],3a仍在3b之前。

冒泡排序的变种：双向冒泡与递归实现

双向冒泡（鸡尾酒排序）

同时从前往后和从后往前扫描,每次在一轮中确定最大和最小元素。

def cocktail_sort(arr):
    n = len(arr)
    start, end = 0, n - 1
    swapped = True
    while swapped:
        swapped = False
        # 正向冒泡（将最大值移到尾部）
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        end -= 1
        if not swapped:
            break
        # 反向冒泡（将最小值移到头部）
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        start += 1
    return arr

递归实现（不推荐，仅用于理解）

递归实现会消耗栈空间,且性能不如迭代。

def bubble_sort_recursive(arr, n):
    if n == 1:
        return
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
    bubble_sort_recursive(arr, n - 1)

实战案例：对用户输入的成绩列表进行排序

场景：老师需要将全班学生的成绩从低到高排序,并显示排名。

def get_scores():
    scores = []
    while True:
        user_input = input("请输入成绩（输入q结束）：")
        if user_input.lower() == 'q':
            break
        try:
            score = float(user_input)
            if score < 0 or score > 100:
                print("成绩应在0-100之间，请重新输入")
                continue
            scores.append(score)
        except ValueError:
            print("请输入合法数字或q退出")
    return scores
scores = get_scores()
if scores:
    sorted_scores = bubble_sort_optimized(scores.copy())
    print("\n=== 成绩排名（升序）===")
    for idx, s in enumerate(sorted_scores, 1):
        print(f"第{idx}名：{s:.1f}分")
else:
    print("未输入任何成绩")

输出示例：

第1名：56.0分  
第2名：72.5分  
第3名：88.0分  
第4名：95.0分

与Python内置排序的性能对比

使用timeit模块测试10万个随机整数的排序耗时：

import timeit
import random
data = random.sample(range(1, 1000001), 100000)
# 测试冒泡排序（优化版）
time_bubble = timeit.timeit(
    "bubble_sort_optimized(data.copy())",
    globals=globals(),
    number=1
)
# 测试内置排序
time_builtin = timeit.timeit(
    "sorted(data)", 
    globals=globals(), 
    number=1
)
print(f"冒泡排序耗时：{time_bubble:.4f}秒")
print(f"内置排序耗时：{time_builtin:.4f}秒")

典型结果（仅供参考，取决于硬件）：

冒泡排序：约15-25秒
内置排序（Timsort）：约0.02秒
差距近千倍,再次说明实际开发中应避免使用冒泡排序。

总结与学习建议

核心要点	学习建议
理解双循环嵌套结构	手动画出每次循环的状态变化（纸笔模拟）
掌握优化技巧（标志位、记录最后交换）	对比优化前后的代码差异，思考为什么能提升效率
认清O(n²)的局限性	建议继续学习插入排序、快速排序、归并排序
稳定排序的适用场景	当需要保持相等元素的相对顺序时（如多关键字排序）
面试考点（边界条件）	自己测试空列表、单元素列表、已排序列表