排序：冒泡排序与内置 sorted

这是什么：排序 = 把一堆乱序数据排整齐的手艺，也是学算法的第一堂必修课。

为什么用：上一章说"二分查找要求列表有序"——没有排序，二分查找就用不上，查找只能一个一个翻，数据量一大就卡住。

如何用：本章先手写冒泡排序，看一遍 92 怎么冒到队尾，再对比 Python 内置的 sorted()。

冒泡排序：大的往后冒

思路特别直白：从头开始两两比较相邻的数，大的换到后面；一轮走完，最大的数就"冒"到了末尾。重复几轮，整个列表就有序了。

拿 [88, 5, 92, 30, 71] 走第一轮，盯紧 92 怎么冒到队尾：

比较位置	比较前	比较后	动作
第 1、2 位	88, 5	5, 88, 92, 30, 71	88 > 5，交换
第 2、3 位	88, 92	5, 88, 92, 30, 71	不用换
第 3、4 位	92, 30	5, 88, 30, 92, 71	92 > 30，交换
第 4、5 位	92, 71	5, 88, 30, 71, 92	92 > 71，交换

一轮结束，最大的 92 冒到了最后。完整实现：

scores = [88, 5, 92, 30, 71]

n = len(scores)
for i in range(n - 1):            # 一共冒 n-1 轮
    for j in range(n - 1 - i):    # 每轮两两比较，冒过的不再比
        if scores[j] > scores[j + 1]:
            scores[j], scores[j + 1] = scores[j + 1], scores[j]   # 交换

print(scores)

你会看到：

[5, 30, 71, 88, 92]

两两比较、一轮定一个最大值——这是 O(n²)，数据一大就慢，但它是理解排序思想的最佳入门教材。

sorted() 与 .sort()：日常干活用它俩

真实项目里没人手写冒泡，Python 内置的排序又快又好用。但两种用法有区别：

scores = [88, 5, 92, 30, 71]

print(sorted(scores))    # 返回排好的新列表
print(scores)            # 原列表果然没动
scores.sort()            # 原地修改，自己就变有序
print(scores)

你会看到：

[5, 30, 71, 88, 92]
[88, 5, 92, 30, 71]
[5, 30, 71, 88, 92]

sorted() 造新列表，.sort() 改自己——想保留原始顺序用前者，不在乎原样用后者。要倒序，加 reverse=True。

key 参数：按哪一列排

排序的不只是数字。给它一个 key，告诉 Python"按什么排"：

students = [
    ("小青蛙", 92),
    ("阿呆", 88),
    ("阿瓜", 71),
]

by_score = sorted(students, key=lambda s: s[1], reverse=True)
for name, score in by_score:
    print(name, score)

你会看到：

小青蛙 92
阿呆 88
阿瓜 71

lambda s: s[1] 读作"给我一个元素 s，取它的第 1 位（分数）来比"，reverse=True 让分数从高到低。

逐概念解读

写法	作用
`range(n - 1 - i)`	已冒到队尾的不用再比，每轮少比一个
`a, b = b, a`	Python 的交换写法，一行换两个变量
`sorted(xs)` / `xs.sort()`	造新列表排 / 原地修改
`key=lambda s: s[1]`	指定按元素的哪一部分排序

记忆口诀

冒泡：两两比，大右移，一轮定一个。内置：sorted 新、sort 原地，key 管按哪列。

动手改

在冒泡的内层循环后面加一行 print(scores)，看列表每轮怎么变化
把冒泡的 > 改成 <，看看排出的是从大到小还是从小到大
用 sorted(students, key=...) 按名字排序（提示：key 取 s[0]）

下一章：递归，函数自己调用自己 🐸