波仔
🧠 第三章 编程语言
📄 一句话概括

20 个数：冒泡比较 180 次、选择 190 次、插入 123 次。 到 n=2000，冒泡 318.4 毫秒、sorted 只要 0.22 毫秒——差一千多倍。

📝 本节和前面几节的关系

上一节算提成，这一节排数字。 排序是所有数据处理的入口：去重要先排、找中位数要先排、标注结果核对也常要先排。

一、三种手写法在比什么

Demo 写了三种最基础的排序，每一种都统计了两个量：比较次数、搬动次数。 - 冒泡：相邻两个比，大的往后挪。20 个数比 180 次、搬 108 次。 - 选择：每轮找最小的放到前面。比 190 次，但只搬 16 次。 - 插入：像理牌，把每张插到合适位置。比 123 次、搬 108 次。 三种都比 190 次以下——因为数据进来时就已经有点乱中有序了， 冒泡还加了「一轮没换就收工」的提前退出。 选择排序的比较次数是固定的 n(n-1)/2，本例 190 次，一次不少。它的优点是搬动少：只有 16 次。 搬动贵、比较便宜的场景就该用它。

二、规模一大就藏不住

20 个数看不出差距，100 个开始露头，2000 个就彻底分家： - n=100：冒泡 0.5、选择 0.3、插入 0.3 毫秒，sorted 0.01 毫秒。 - n=500：16.2、9.8、7.9 对 0.05 毫秒。 - n=2000：318.4、149.6、167.8 对 0.22 毫秒。 2000 个数时，sorted 比冒泡快一千倍以上。 这不是常数优化能追的——手写的那三种是 O(n²)，sorted 用的 Timsort 是 O(n log n)。 所以结论很直接：生产代码里永远用 sorted 或 list.sort()。 手写排序是用来理解算法的，不是用来干活的。

三、稳定性：同分的两个人会不会换位

Demo 用四个人演示：张三 90、李四 85、王五 90、赵六 85。 按分数降序排完，结果是 张三、王五、李四、赵六。 两个 90 分的相对次序没变，两个 85 分的也没变——这叫稳定排序。 为什么重要？标注数据里常要「先按置信度排，同置信度的保持原始顺序」。 排序不稳定，同一批数据两次跑出来的顺序就不一样，人工复核的结论也跟着飘。 Python 的 sorted 是稳定的。 所以想「分数降、同分按姓名升」，写 key=lambda t: (-t[1], t[0]) 一次排完就行，不需要排两遍。

四、两个实用提醒

第一，别在原地改。 sorted(a) 返回新列表，a.sort() 改原列表。 数据预处理里混用这两者，是最常见的「原始数据被覆盖」来源。 第二，比较函数用 key 不用 cmp。 Python 3 去掉了 cmp 参数，要按自定义规则排， 就构造一个能比较的 key。本例的 -t[1] 就是把「分数降序」翻译成「负分升序」。 这两条看着琐碎，但每一条都对应过真实事故：前者让原始数据被改，后者让排序规则写不出来。

五、动手 Demo：三种手写排序与内置的性能差

造 20 个随机数，用冒泡、选择、插入各排一遍，统计比较次数与搬动次数， 并与 sorted 校验结果是否一致；再把规模放大到 100／500／2000，量四种写法的耗时； 最后演示稳定排序与复合 key。

def bubble(a):
    a = list(a)
    for i in range(len(a) - 1):
        done = True
        for j in range(len(a) - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                done = False
        if done:
            break
    return a

for n in (100, 500, 2000):
    d = [random.randint(1, 9999) for _ in range(n)]
    # 四种写法各跑一次，记毫秒

by_score = sorted(people, key=lambda t: -t[1])

实跑输出：

--------------------------------------------------------------------
实例 2：由小到大排数字，三种手写法和内置的差距
--------------------------------------------------------------------
  原始 20 个数             [655, 432, 440, 773, 742, 105, 68, 376, 715, 475, 384, 45, 623, 681, 175, 605, 353, 336, 274, 728]

  算法       比较次数   搬动次数   结果对不对
  ------------------------------------------
  冒泡            180        108   True
  选择            190         16   True
  插入            123        108   True
  sorted()       内置       内置   基准
  排完                     [45, 68, 105, 175, 274, 336, 353, 376, 384, 432, 440, 475, 605, 623, 655, 681, 715, 728, 742, 773]

  规模一大，差距就藏不住了：
     n   冒泡(ms)   选择(ms)   插入(ms)   sorted(ms)
  -------------------------------------------------
   100        0.9        0.4        0.3         0.01
   500       15.4        9.3        8.7         0.05
  2000      324.7      152.3      169.1         0.23

  稳定性：两个同分的人，排完还按不按原来顺序？
  按分数降序               [('张三', 90), ('王五', 90), ('李四', 85), ('赵六', 85)]
  两个 90 分的相对次序     保持原序（这就是稳定）
  Python 的 sorted 是稳定排序；要「分数降、同分按姓名升」，
  写 key=lambda t: (-t[1], t[0]) 一次排完，不要排两遍。

20 个数那张表：冒泡 180 次比较、108 次搬动；选择 190 次比较、只搬 16 次； 插入 123 次比较、108 次搬动。三个结果都判对了。 选择排序的比较次数正好是 20×19/2 = 190，一次不多一次不少——它不管数据长什么样都要比这么多。 规模表最能说明问题：n=2000 时冒泡 318.4 毫秒，sorted 0.22 毫秒。 同一条数据、同一台机器，差三个数量级。 稳定性那两行：排完是 张三、王五、李四、赵六，两个 90 分、两个 85 分的原始次序都没动。

30 秒实验

  1. 把 20 个数换成已经排好的顺序，重跑一遍，看冒泡的比较次数掉到多少。
  2. 给四个人加一个「部门」字段，用复合 key 排成「部门升、分数降」。
  3. 想一想：为什么选择排序搬动次数最少，却不一定最快？

常见误区

  1. 「自己写的排序更懂业务」——sorted 是一千倍的差距，跟懂不懂业务无关。
  2. 「sorted 和 sort 一样」——一个返回新列表，一个改原列表。
  3. 「顺序差不多就行」——不稳定排序让同一批数据两次结果不同，复核就没法做。
自测三问（点开对答案） 1. 选择排序的比较次数为什么是固定的？ —— 它不管数据怎么排都要把剩下的全部比一遍，次数是 `n(n-1)/2`。 2. n=2000 时冒泡和 `sorted` 差多少？ —— 318.4 毫秒 对 0.22 毫秒，相差三个数量级。 3. 怎么实现「分数降序、同分按姓名升序」？ —— `key=lambda t: (-t[1], t[0])`，一次排完，不要排两遍。

排序练完，下一个实例换个思路——用递推算数列，看四种算法的速度差。

相关笔记