异常教程

使用 Python 实现冒泡排序算法（手把手讲解）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

在编程世界中，排序算法是算法学习的基石之一。无论是处理数据、优化性能，还是解决实际问题，掌握排序算法的核心思想都至关重要。冒泡排序作为经典排序算法的代表，因其直观的逻辑和简单的实现方式，成为许多开发者入门算法的首选。本文将深入讲解如何使用 Python 实现冒泡排序算法，通过循序渐进的案例分析和代码示例，帮助读者理解其原理，并掌握如何在实际项目中应用这一算法。

冒泡排序的核心思想

冒泡排序（Bubble Sort）的名字来源于其工作原理的直观形象：就像气泡在液体中逐渐上浮一样，排序过程中较小的元素会像气泡一样逐渐“冒”到数组的顶端。具体来说，冒泡排序通过重复遍历待排序的列表，依次比较相邻元素的大小，若顺序不正确则交换它们的位置。这一过程会持续进行，直到整个列表完全有序。

形象比喻：同学排队的例子

想象一个班级排队的场景：同学们按照身高从矮到高排列，但初始时队列是混乱的。冒泡排序的过程类似于这样的调整：

  1. 从队列的第一个同学开始，依次比较相邻两位同学的身高。
  2. 如果前面的同学比后面的同学高，则两人交换位置。
  3. 完成一轮遍历后，最高个子的同学会“沉到底部”，而最矮的同学则会“冒”到队列的最前面。
  4. 重复这一过程，直到所有同学都按正确顺序排列。

这种逐层比较和交换的方式，正是冒泡排序的核心逻辑。

算法实现步骤详解

接下来，我们将逐步拆解冒泡排序的实现步骤，并通过 Python 代码进行演示。

步骤 1：初始化待排序列表

首先，我们需要一个待排序的列表。例如：

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

步骤 2：外层循环控制遍历次数

冒泡排序需要进行多轮遍历。每一轮遍历会将当前未排序部分的最大元素“沉”到末尾。因此，外层循环的次数等于列表长度减一：

n = len(unsorted_list)  
for i in range(n - 1):  
    # 内层循环逻辑

步骤 3：内层循环执行相邻元素比较与交换

内层循环负责逐个比较相邻元素，并在必要时交换它们的位置：

for j in range(0, n - i - 1):  
    if unsorted_list[j] > unsorted_list[j + 1]:  
        unsorted_list[j], unsorted_list[j + 1] = unsorted_list[j + 1], unsorted_list[j]

完整代码示例

将上述步骤整合后，完整的冒泡排序代码如下：

def bubble_sort(arr):  
    n = len(arr)  
    for i in range(n - 1):  
        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  

test_list = [64, 34, 25, 12, 22, 11, 90]  
print("原始列表:", test_list)  
bubble_sort(test_list)  
print("排序后列表:", test_list)

运行结果：

原始列表: [64, 34, 25, 12, 22, 11, 90]  
排序后列表: [11, 12, 22, 25, 34, 64, 90]

算法优化：提前终止未完成的遍历

标准冒泡排序的时间复杂度为 O(n²)，在最坏情况下（如逆序列表）性能较低。为了提升效率，可以引入一个标志位，记录某一轮遍历中是否发生了交换。若某一轮中没有发生任何交换，说明列表已完全有序，此时可提前终止排序：

def optimized_bubble_sort(arr):  
    n = len(arr)  
    for i in range(n - 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  
        if not swapped:  
            break  
    return arr

优化效果对比

列表类型标准冒泡排序优化后冒泡排序
完全无序O(n²)O(n²)
部分有序O(n²)O(n)
完全有序O(n²)O(n)

算法复杂度分析

时间复杂度

  • 最坏情况：列表逆序排列，时间复杂度为 O(n²)。
  • 平均情况：时间复杂度仍为 O(n²)。
  • 最好情况：列表已有序，优化后的时间复杂度为 O(n)。

空间复杂度

冒泡排序仅需一个临时变量用于元素交换，因此空间复杂度为 O(1)。

稳定性

冒泡排序是一种稳定的排序算法，即相等元素的相对位置在排序前后不会改变。

实际应用场景与局限性

适用场景

  1. 小规模数据排序：当数据量较小时，冒泡排序的实现简单性和稳定性使其成为合理选择。
  2. 教学示例：因其逻辑直观，常用于算法入门教学。

局限性

  1. 性能不足：对于大规模数据（如 n > 1000），冒泡排序效率明显低于快速排序、归并排序等算法。
  2. 内存占用固定：虽然空间复杂度低，但在需要频繁交换元素时可能影响局部性。

扩展思考：冒泡排序的变体

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

鸡尾酒排序通过在相邻两轮遍历中交替从左到右和从右到左比较元素，进一步减少交换次数。其实现代码如下：

def cocktail_sort(arr):  
    n = len(arr)  
    start = 0  
    end = 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  
        if not swapped:  
            break  
        end -= 1  
        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

总结

通过本文的讲解，我们系统性地学习了如何使用 Python 实现冒泡排序算法。从核心思想的比喻到代码的逐层解析，再到优化方法与复杂度分析，读者应已掌握这一算法的全貌。尽管冒泡排序在性能上并非最优，但它作为算法学习的起点，帮助开发者理解排序逻辑的本质。

在实际开发中，若需处理大规模数据，建议选择更高效的排序算法；但对于教学、小规模数据或需要稳定性的场景，冒泡排序仍是一个值得掌握的工具。通过不断练习与实践，读者可以逐步提升算法思维，并为后续学习更复杂的算法打下坚实基础。

希望本文能成为您探索算法世界的第一个坚实脚印！

最新发布

查看更多文章