波仔
💻 第五章 与算法成为好朋友的七个要点
📄 一句话概括

写代码前先在纸上把例子手工排一遍——冒泡排序手工排五张卡片，三处要点自然浮出，写代码时每行都知道自己在干嘛。

📝 本节和前面几节的关系

七个要点压轴的一条，也是回到学习法的一条：动手敲之前，先动手排。

一、纸上排一遍的价值

以冒泡排序为例（把 5、3、4、1、2 排成升序）：规则是相邻两两比较，大的往右换，一轮下来最大的数【冒】到最右。 在纸上把每一轮的数组状态写出来，三轮排完——这比你直接读三遍代码记得牢。 更关键的是，纸上排的过程会自己暴露算法要点：每轮比几次？什么时候能提前结束？——这些问题手工排过自然有答案。

二、手工排出来的三处要点

相邻交换：只换相邻的两个，别的都不动——对应代码里的 if 与交换语句； 每轮冒出一个最大值：第 i 轮后右侧 i 个已就位——对应外层循环 n-1 轮、内层逐轮缩短； 早停：某一轮一次都没交换，说明已经有序——对应 swapped 标志的优化。 三处要点手工排时全都【看得见】，这正是先纸上后代码的意义。

三、七个要点的收官

回望本章：明确有限（5.2）→ 机械视角（5.3）→ 典型算法（5.4）→ 借机器速度（5.5）→ 技巧提速（5.6）→ 找规律（5.7）→ 先在纸上想（5.8）。 七个要点连起来是一条完整的解题纪律——第六章的【数据结构】将从【数据的摆法】一侧接棒。

四、动手 Demo：冒泡排序逐轮纸上排

把五张卡片的每一轮状态打出来，亲手【看】冒泡发生。

# 冒泡排序: 相邻比较, 大的右移
a = [5, 3, 4, 1, 2]
print("初始:", a)
for i in range(len(a) - 1):
    for j in range(len(a) - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
    print("第 %d 轮:" % (i + 1), a)

实跑输出：

--------------------------------------------------------------------
要点 7——先在纸上考虑算法：冒泡排序手工排
--------------------------------------------------------------------

动手写代码之前，先在纸上把例子手工排一遍——这一节演示【纸上排法】：

初始: [5, 3, 4, 1, 2]
    第 1 轮冒完: [3, 4, 1, 2, 5]  (最大的数 5 冒到了右侧)
    第 2 轮冒完: [3, 1, 2, 4, 5]  (最大的数 4 冒到了右侧)
    第 3 轮冒完: [1, 2, 3, 4, 5]  (最大的数 3 冒到了右侧)
    第 4 轮冒完: [1, 2, 3, 4, 5]  (最大的数 2 冒到了右侧)

手工排完，冒泡的三个要点自然浮出来：
  要点                   纸上的表现             代码对应
  ---------------------------------------------------------------------
  相邻两两比较           看到 5 和 3 换位置     if a[j] > a[j+1]: 交换
  每轮冒出一个最大值     右侧渐渐排好           外层循环 n-1 轮
  早停优化               某轮没换说明已有序     swapped 标志

在纸上排过一遍的人，写代码时每行都知道自己在干嘛——
这就是要点 7：**先在纸上考虑，再让机器执行**。

注意每轮右侧渐渐多出一个【就位】的数——这就是【冒泡】名字的由来。 试着在纸上只看每轮首尾，预测下一轮结果——预测对了，说明排序逻辑已在你脑中跑通。

30 秒实验

  1. 换个数组（如 9、7、5）在纸上手工冒泡，再跑代码核对每一轮。
  2. 给冒泡加 swapped 标志做早停优化——对已有序的数组只排一轮。

常见误区

  1. 不排例子直接背代码——背得出写不对，因为没见过中间状态。
  2. 以为冒泡每轮比 n 次——每轮之后右侧就位一个，内层循环逐轮缩短。
自测三问（点开对答案） 1. 冒泡排序的规则是什么？ —— 相邻两两比较，大的往右换；每轮把最大值冒到未排序部分的最右。 2. 手工排一遍能发现哪三处要点？ —— 相邻交换、每轮冒出一个最大值、某轮无交换即可早停。 3. 为什么【先在纸上考虑】排七个要点的压轴？ —— 它是前面所有要点落地的方法——任何算法都该先手工推再落代码。

相关笔记