第 11 课：冒泡排序

所属模块：排序算法 难度：beginner 标签：bubble-sort, swap, stable

1. 学习目标

完成本课学习后，你将能够：

1. 理解冒泡排序的基本思想和工作原理。
2. 实现一个标准的冒泡排序算法函数。
3. 分析冒泡排序的时间复杂度和空间复杂度。
4. 识别冒泡排序的“稳定性”特性。
5. 了解冒泡排序的适用场景与局限性。

2. 核心概念

什么是排序？ 想象一下，你有一堆杂乱无章的数字卡片，你想把它们从小到大（升序）或从大到小（降序）排好。这个过程就叫排序。冒泡排序是最简单、最直观的排序算法之一。

“冒泡”从何而来？ 想象一串水中的气泡，大的气泡会慢慢地上升到水面。在冒泡排序中，每次遍历，数组中较大的元素就像“气泡”一样，通过相邻元素的比较和交换，逐步“浮”到数组的末尾（或开头，取决于排序方向）。

核心步骤：

1. 比较：从数组的第一个元素开始，依次比较相邻的两个元素。
2. 交换：如果前一个元素比后一个元素大（对于升序排序），就交换它们的位置。
3. 重复：对每一对相邻元素做同样的工作，从开始第一对到最后一对。这步做完后，最后的元素就是最大的数。
4. 缩小范围：针对所有元素重复以上的步骤，除了最后一个（因为它已经在正确位置了）。每次遍历后，未排序部分的“边界”就向前提前一位。
5. 终止：当没有任何一对数字需要比较时，排序完成。

可以把它想象成在教室里按身高从低到高排队。每轮从队伍开头走一遍，让相邻的两个人如果顺序不对就互相换位。一轮结束后，最高的同学就“冒泡”到了队尾。然后我们忽略队尾的同学，对前面的同学再进行一轮比较，以此类推。

3. 代码示例

下面是用Python实现的标准冒泡排序算法，我们将其封装成一个函数。

def bubble_sort(arr):
    """
    使用冒泡排序算法对列表进行升序排序（原地排序）。
    参数: arr - 一个可比较元素的列表
    返回: 排序后的列表 (原地修改)
    """
    n = len(arr)
    # 外层循环控制需要进行多少轮“冒泡”。n-1轮就足够了。
    for i in range(n - 1):
        # 一个优化标志：如果在某一轮中没有发生任何交换，说明数组已经有序，可以提前结束。
        swapped = False
        # 内层循环进行相邻元素的比较和交换。
        # 注意：每完成一轮外层循环(i)，最大的i个元素已经就位到末尾，所以内层循环的范围是 n-1-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] # Python的交换语法
                swapped = True # 标记发生了交换
        # 如果在当前轮没有发生交换，说明列表已有序，提前退出循环
        if not swapped:
            break
    return arr

# 测试代码
if __name__ == "__main__":
    my_list = [64, 34, 25, 12, 22, 11, 90]
    print("原始列表:", my_list)
    sorted_list = bubble_sort(my_list)
    print("排序后列表:", sorted_list)

运行结果：

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

手动演示一轮排序过程（以列表 [5, 1, 4, 2, 8] 为例，升序）：

• 第1轮 (i=0): 目标是把最大值“冒泡”到最后。
  • 比较(5,1) -> 交换 -> [1, 5, 4, 2, 8]
  • 比较(5,4) -> 交换 -> [1, 4, 5, 2, 8]
  • 比较(5,2) -> 交换 -> [1, 4, 2, 5, 8]
  • 比较(5,8) -> 不交换 -> [1, 4, 2, 5, 8]
  • 结果：最大的8已到末尾，但列表仍未完全排序。

4. 实践练习

练习1：基础实现 修改上述bubble_sort函数，使其能够进行降序排序（从大到小）。并用列表 [17, 24, 9, 13, 5] 测试你的函数。 预期输出： [24, 17, 13, 9, 5]

练习2：手动计算 对于列表 [3, 1, 5, 2, 4]，请手动写出冒泡排序第一轮（i=0） 完整的比较和交换过程，并给出第一轮结束后列表的状态。

练习3：复杂度分析

1. 在什么情况下，冒泡排序的时间复杂度最差（O(n²)）？此时输入列表是什么样的？
2. 在什么情况下，冒泡排序的时间复杂度最好（O(n)）？此时输入列表是什么样的？（提示：考虑我们加入的优化标志 swapped）

5. 常见错误

1. 内层循环边界错误：这是最常见的错误。内层循环的终止条件应该是 n - i - 1，而不是 n - 1。如果写成 n - 1，每一轮都会重新比较已经就位的末尾元素，导致效率低下且逻辑冗余。忘记 -i 会让算法失去“每轮减少一次比较”的优化。
2. 忽略交换逻辑：在if条件成立时，必须同时完成两个元素的值交换。初学者有时会写成 arr[j] = arr[j+1]，这样会丢失arr[j]的原值。在Python中，a, b = b, a 是标准且优雅的写法。
3. 提前终止条件缺失：没有使用swapped标志来提前终止循环。这虽然不影响算法的正确性，但会使其在输入数据已经有序或部分有序时，无法利用这一特性来提升效率，白白执行不必要的循环。
4. 概念混淆：将“冒泡排序”和接下来要学的“选择排序”搞混。记住：冒泡排序通过相邻交换让最大值“浮”上来；选择排序是找到最小值后直接放到最前面。

6. 小结

• 核心思想：重复地遍历待排序的列表，依次比较相邻元素，并在顺序错误时交换它们，直到没有元素需要交换为止。
• 关键点：理解“冒泡”的过程，即每轮遍历将当前未排序部分的最大（或最小）元素移动到其最终位置。
• 时间复杂度：最坏情况和平均情况均为 O(n²)，最好情况（列表已有序）为 O(n)。
• 空间复杂度：O(1)，因为它只需要常数级别的额外空间，是原地排序算法。
• 稳定性：稳定。因为相等的元素不会发生交换，所以它们的原始相对顺序得以保持。
• 适用性：由于时间复杂度较高，冒泡排序不适合对大规模数据进行排序。它的主要价值在于其简单性，常用于教学，或对非常小的数据集进行排序。