波仔
🧮 第4章 学习算法基础
📄 一句话概括

找最大最小叫打擂台：先让第一个当擂主，后面每个上来打一场。 八个人只要比 7 轮，因为第一个不用跟自己比。 排名排的是「谁第几」，不是把原数组打乱——真实场合往往要保留原始顺序。

📝 本章和前面几章的关系

上一篇求的是「合起来多少」，这一篇求的是「哪一个最突出」。 打擂台这个套路简单到一句话就能说完，但它的边界（比几轮）正好是第 4.1 那个差一错的延续。 排名是它的升级版：不只找第一，要把所有人都排出来。排完还要面对一个新问题——同分怎么办。

一、打擂台：先让第一个当擂主

八个人的分数：78、92、65、92、88、100、47、73。找最高分。 做法：先让第一个（78）当擂主，后面每个上来打一场，比它大就换人。 78 对 92，换人；92 对 65，不变；92 对 92，不变（相等不换）；再对 88、100，100 上位； 最后对 47、73，不动。

结果最高 100。「比它大就换人」这一句就是全部的算法。 找最低分是同一套，把「比它大」改成「比它小」就行。所以最高最低只差一个比较符号。

二、为什么是 7 轮不是 8 轮

八个人，只比了 7 轮。因为第一个是擂主，它不用跟自己打。 这个「少一轮」值得停一下。 它不是省事，是逻辑上必须如此：n 个数之间一共有 n-1 组相邻的比较关系，比 n-1 次就足够定出最大。 演示里那句提醒很实在：少算这一轮不算错， 但写排序时这种「差一轮」会变成差一位——导致最后一个元素永远没被处理。

所以看到「7 轮」不要觉得奇怪，它是 n-1，不是 n。这条规律后面在排序里还会出现。 顺带一句：比较次数是固定的 n-1，跟数据本身长什么样无关。最坏最好都一样快，这是它可爱的地方。

三、排名：排的是名次，不是打乱原数组

有了最高最低，下一步常常是「所有人排第几」。 演示里的做法是记下标，不动原数据：排好的下标是 5、1、3、4、0、7、2、6， 对应的分数从 100 一直排到 47。 为什么不动原数据？因为真实场合经常要保留原始顺序。 比如成绩单按学号录入，你想知道排名，但打印时还得按学号排。

所以工程上的做法是：原数组不动，另外记一张名次表。 这也解释了为什么排序算法有两种：一种直接改数组（就地排序），一种返回新数组。 前者省内存，后者保原样。第 5 章会看到这两种都有。

四、同分怎么办：两种口径

八个人里 92 分出现了两次。这就有了新问题：谁是第 2 名？ 演示里的做法是并列：两个 92 都是第 2 名，下一个 88 直接第 4 名——第 3 名空着。 另一种做法叫密集排名：两个 92 都第 2，下一个 88 就是第 3。名次连续，不跳号。

两种都不算错。 比赛成绩用并列（第三名空着，因为确实有两个人比他强），等级评定用密集（一二三等，中间不该空）。 关键在这一句： 口径必须先定，不然两个人算出来不一样。这和第 4.2 的「月均保留几位」是同一类问题——先定口径， 再谈对错。

五、排名要先比，再换位

自己写排名，路子有两条：一条是「给每个人数一数有多少人比他高」，数出几个就是第几名加一； 另一条是先排序再读位置。 第一条路是两层循环，比较次数是 n 的平方级别；第二条路交给排序，通常快得多。 这也是第 5 章存在的理由。 第一条路有个好处：天然能处理并列。两个 92 都数出「一个比我高」，于是都是第 2 名。

所以选哪条路，取决于你要不要处理并列、数据有多大。小数据求简单，大数据求快。

六、动手 Demo：八个人的最高分、最低分和一张名次表

先打擂台找最高最低，数一数比了几轮。 再按分数从高到低排出下标，看原数组有没有被动过。 最后处理两个 92：并列名次和密集排名各算一遍。

a = [78, 92, 65, 92, 88, 100, 47, 73]

best, worst, cnt = a[0], a[0], 0
for x in a[1:]:
    cnt += 1
    if x > best:
        best = x
    if x < worst:
        worst = x
print('最高', best, '最低', worst, '比了', cnt, '轮')

idx = sorted(range(len(a)), key=lambda i: -a[i])
print('下标', idx)
print('分数', [a[i] for i in idx])
print('原数组', a)

rank, dense, last, d = [], [], None, 0
for rank_no, i in enumerate(idx, 1):
    if a[i] != last:
        d = rank_no
        last = a[i]
    rank.append(d)
print('并列名次', rank)

实跑输出：

--------------------------------------------------------------------
最高分、最低分与排名
--------------------------------------------------------------------


  ① 打擂台：找最大最小
  --------------------------------------------------------------------
  八个人的分数：[78, 92, 65, 92, 88, 100, 47, 73]
  最高 100，最低 47，比了 7 轮
  做法叫打擂台：先让第一个当擂主，后面每个上来打一场。「比它大就换人」这一句就是全部的算法。
  注意这里是 7 轮而不是 8 轮——第一个不用跟自己比。
  少算这一轮不算错，但写排序时这种「差一轮」会变成差一位。

  ② 排名：先比大小，再定名次
  --------------------------------------------------------------------
  按分数从高到低排好的下标：[5, 1, 3, 4, 0, 7, 2, 6]
  对应的分数：[100, 92, 92, 88, 78, 73, 65, 47]
  排序的结果是「谁排第几」，不是把原数组打乱。
  这点很重要：真实场合往往要保留原始顺序，只额外记一张名次表。

  ③ 同分怎么办
  --------------------------------------------------------------------

| 分数 | 名次 | 排序位置 |
|---:|---|---|
| 100 | 第 1 名 | 第 1 个被排到 |
| 92 | 第 2 名 | 第 2 个被排到 |
| 92 | 第 2 名 | 第 3 个被排到 |
| 88 | 第 4 名 | 第 4 个被排到 |
| 78 | 第 5 名 | 第 5 个被排到 |
| 73 | 第 6 名 | 第 6 个被排到 |
| 65 | 第 7 名 | 第 7 个被排到 |
| 47 | 第 8 名 | 第 8 个被排到 |

  92 分出现两次，名次都是第 2，但位置是第 2 个和第 3 个。
  这叫「并列名次」，跳过后面的名次（没有第 3 名）。
  另一种做法是「密集排名」：两个 92 都第 2，下一个直接第 3。
  两种都不算错，看你报表要哪种口径——口径必须先定，不然两个人算出来不一样。

①a[1:] 从第二个开始，所以第一个当擂主不参加比较。这就是 7 轮的来源。 ②相等时不换人（> 不是 >=）。 换成 >= 结果也一样，但会多换几次，在找「第一个最大值」和「最后一个最大值」时就有区别了。 ③sorted(..., key=lambda i: -a[i]) 排的是下标，不是分数。所以最后打印原数组，它一点没变。 ④名次那段用的是「比分」：分数变了名次才加。两个 92 因此拿到同一个名次，下一个 88 直接第 4。

30 秒实验

  1. 把 > 改成 >=，看最高分是哪一个（100 只有一个，试试把数据里改成两个 100）。
  2. 改成「密集排名」：两个 92 都第 2，88 是第 3。要改哪一行？
  3. 用「数有多少人比我高」的办法重写排名，验证结果和现在一样。

常见误区

  1. 「八个人要比八轮。」第一个当擂主，只要 7 轮（n-1）。
  2. 「排名就是把数组排序。」排的是下标/名次，原数组常常要保留。
  3. 「同分就该并列。」并列和密集都对，看口径。定不下来就会两个人算出两个结果。
自测三问（点开对答案） 1. 打擂台为什么只要 n-1 轮？ —— 第一个当擂主，不跟自己比。n 个数之间只有 n-1 组比较关系。 2. 为什么排名常常要保留原数组？ —— 原顺序往往另有用途（学号、录入顺序）。所以要另记一张名次表。 3. 并列名次和密集排名差在哪？ —— 并列会跳号（两个第 2，下一个第 4）；密集不跳号（下一个第 3）。

合起来多少、谁最高都解决了。 下一节是两个更「工程」的题：按科目求和，和算两个时刻差多久——顺带说说 2038 年那件事。

相关笔记