冒泡排序：让大数像泡泡一样浮到末尾

什么是冒泡排序？

想象一下你有一排小朋友按身高从矮到高排队，但是队伍现在乱糟糟的。你想把最高的同学移到最右边。冒泡排序就像吹泡泡一样——每次比较相邻两个小朋友，如果左边比右边高，就交换他们的位置。这样，最高的“气泡”就会慢慢“浮”到队伍的末尾。重复这个过程，直到所有小朋友都按身高排得整整齐齐。

冒泡排序是一种基于比较的排序算法，它通过不断“冒泡”把最大的元素送到末尾，整个过程就像水里的气泡上升一样。它特别简单，适合用来理解排序的基本思想，也适合数据量很少的时候使用。

原理分解：一步一步来

1. 核心步骤

从数组的第一个元素开始，依次比较相邻的两个数。
如果左边的数比右边大，就交换它们（让大的往右走）。
每一轮结束后，当前未排序部分中最大的数就会“浮”到最右边。
重复上述步骤，但是每轮比较的范围缩小一个（因为末尾已经排好了）。
如果某一轮没有发生任何交换，说明数组已经有序，可以提前结束。

2. 结合生活中的例子

假设我们有四个小朋友的分数（满分10分）：score = [5, 3, 8, 1]，我们按分数从小到大排。

第一轮：

比较5和3 → 5>3，交换 → [3, 5, 8, 1]
比较5和8 → 5<8，不交换 → [3, 5, 8, 1]
比较8和1 → 8>1，交换 → [3, 5, 1, 8]
第一轮结束，最大的8已经“浮”到了末尾。

第二轮：

比较3和5 → 3<5，不交换 → [3, 5, 1, 8]
比较5和1 → 5>1，交换 → [3, 1, 5, 8]
第二轮结束，5来到了倒数第二的位置。

第三轮：

比较3和1 → 3>1，交换 → [1, 3, 5, 8]
第三轮结束，全部有序。

你看，就像泡泡一样，每次最大的数都慢慢漂到了右边。

新手最容易犯的错误

错误1：比较范围没有递减

很多同学会写成 for j in range(n-1)，导致每一轮都从头比较到末尾，这样不仅浪费时间，而且已经排好的最大数又会被比较，甚至可能被交换回去。
正确做法：每轮比较次数 n-1-i，i是已经完成的轮数。

错误2：忘记用优化标记（swapped）

如果不加 swapped 标记，哪怕数组已经有序，程序仍然会傻傻地跑完所有轮次。虽然结果没错，但白白做了很多无用功。
正确做法：每轮开始时设 swapped=False，发生交换就设为 True；如果一轮结束 swapped 还是 False，直接 break。

错误3：把 `arr[j]` 和 `arr[j+1]` 比较方向弄反

如果想从小到大排序，当 arr[j] > arr[j+1] 时交换；如果想从大到小，就改成 arr[j] < arr[j+1] 时交换。

完整可运行的Python代码

下面是一段完整的代码，包含输入输出，并且每行变量都有中文注释：

def bubble_sort(arr):
    """对数组进行冒泡排序（从小到大）"""
    n = len(arr)                     # 数组长度
    for i in range(n - 1):           # 需要 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

# ---------- 测试 ----------
# 让用户输入一串数字，用空格分隔
input_str = input("请输入一串整数，用空格分隔：")
nums = [int(x) for x in input_str.split()]  # 转换成整数列表

print("排序前:", nums)
bubble_sort(nums)
print("排序后:", nums)

运行示例：

请输入一串整数，用空格分隔：5 3 8 1
排序前: [5, 3, 8, 1]
排序后: [1, 3, 5, 8]

你也可以在代码里直接测试：

# 也可以用现成的列表测试
scores = [5, 3, 8, 1]
bubble_sort(scores)
print(scores)  # 输出 [1, 3, 5, 8]

小贴士：何时用冒泡排序？

数据非常少（比如10个以内）：冒泡排序代码简洁，容易写对。
数据基本有序：用了 swapped 优化后，几乎只要一轮就完成，速度很快（接近 O(n)）。
你只是想理解排序原理：冒泡排序是最直观的入门算法。
不推荐：数据量很大（比如几千个）时，冒泡排序非常慢（最坏 O(n²)）。这时候应该用更快的算法，比如快速排序、归并排序等。

冒泡排序