复习:我们学到哪里了 5 分钟
- 线性查找从第 1 行开始沿着列表走,直到找到想要的东西。
- 最坏的时候,它要检查每一行。“不在里面”永远是最坏的情况。
- 排好顺序的列表能让你早点放弃。
快问快答
第 1 行是力量 4 的 Bat。第 2 行是力量 9 的 Dragon。你想让 Dragon 在最上面,所以你把第 2 行写到第 1 行上。Bat 怎么了?
看答案
它不见了。现在两行都是 Dragon。这就是今天的第一个问题。修好它很简单:先把其中一个放到别的地方拿着。
今天的主题 3 分钟
- 交换两行,以及为什么需要第三个框
- 一轮:把每一对相邻的牌都比一次
- 冒泡排序:一轮一轮地做,直到有一轮没有交换
- 一次交换好几个一起走的列表
学习目标
上完这节课,你能够:
- 交换列表的两行,而且不弄丢任何一行。
- 写一个冒泡排序,列表一排好就停下来。
- 说出它花了多少功夫,以及为什么差不多排好的列表更省事。
学一学:最强的牌走到最上面 30 分钟
1 · 交换,还有第三个框
这里有两行,顺序反了。你不能直接把一行抄到另一行上。你把第 2 行写进第 1 行时,第 1 行原来的值就没了。现在你有两张一样的牌。
所以你要先拿着其中一个。在现实中,你会用另一只手拿起一张牌。在 Scratch 里,另一只手就是一个变量:
set [hold power v] to (item (1) of [powers v])
replace item (1) of [powers v] with (item (2) of [powers v])
replace item (2) of [powers v] with (hold power)
怎么用: 点绿旗,看左边的框。hold 变量就是第三只手。
2 · 一轮
现在沿着整个牌组都这样做。比第 1 行和第 2 行,然后第 2 行和第 3 行,然后第 3 行和第 4 行。只要下面那张更大,就把它们换过来。
set [i v] to (1)
repeat ((length of [powers v]) - (1))
if <(item (i) of [powers v]) < (item ((i) + (1)) of [powers v])> then
set [hold name v] to (item (i) of [names v])
set [hold power v] to (item (i) of [powers v])
set [hold pic v] to (item (i) of [pics v])
replace item (i) of [names v] with (item ((i) + (1)) of [names v])
replace item (i) of [powers v] with (item ((i) + (1)) of [powers v])
replace item (i) of [pics v] with (item ((i) + (1)) of [pics v])
replace item ((i) + (1)) of [names v] with (hold name)
replace item ((i) + (1)) of [powers v] with (hold power)
replace item ((i) + (1)) of [pics v] with (hold pic)
end
change [i v] by (1)
end
((length of [powers v]) - (1)),是因为最后一行下面没有东西可以比。一轮不能把牌组排好。但是最大的那张牌总会走到最上面。每次比较它都赢,所以它一直往上走。
怎么用: 点绿旗,看一轮从牌组上面走到下面。然后读一读列表框。好一些了,但还没排完。
3 · 一轮一轮做,直到什么都不动
所以再做一轮。再做一轮。如果整整一轮都没有交换,列表就排好了。列表自己会告诉你:
set [swapped v] to (1)
repeat until <(swapped) = (0)>
set [swapped v] to (0)
set [i v] to (1)
repeat ((length of [powers v]) - (1)) // one pass, as above
if <(item (i) of [powers v]) < (item ((i) + (1)) of [powers v])> then
set [swapped v] to (1)
end
change [i v] by (1)
end
end
swapped 设成 1,这样第一轮一定会做。这就是冒泡排序。它叫这个名字,是因为大的值会像饮料里的泡泡一样往上冒。
4 · 三个列表,一次交换
🔥 你的卡牌是三个一起走的列表。也就是说,每个列表的第 1 行是同一张牌。一次交换必须把三个列表的行都换过来。不然,Dragon 会留着自己的名字,却丢掉它的 9:
set [hold name v] to (item (i) of [names v])
set [hold power v] to (item (i) of [powers v])
set [hold pic v] to (item (i) of [pics v])
replace item (i) of [names v] with (item ((i) + (1)) of [names v])
replace item (i) of [powers v] with (item ((i) + (1)) of [powers v])
replace item (i) of [pics v] with (item ((i) + (1)) of [pics v])
replace item ((i) + (1)) of [names v] with (hold name)
replace item ((i) + (1)) of [powers v] with (hold power)
replace item ((i) + (1)) of [pics v] with (hold pic)
基础任务:给牌组排名 24 分钟
打开你的牌组。你要把它排好顺序,力量大的在前面。
第 1 步:几个框
- 建好
i、swapped、swaps,还有三个 hold:hold name、hold power、hold pic。 - 把 names 和 powers 两个列表并排显示出来。
第 2 步:一次交换
- 为第 1 行和第 2 行搭好九块积木的交换,数字直接打进去。
- 运行它。检查两个列表是不是一起动了。
第 3 步:让它用 i
- 把 1 换成
(i),把 2 换成((i) + (1))。 - 用手把
i设成 3,运行一下检查。
第 4 步:一轮
- 用 if 把交换包起来,再用
repeat ((length of [powers v]) - (1))把 if 包起来。 - 在 repeat 前面把
i设成 1。在循环的最下面给它加 1。 - 运行一次,读一读列表。好一些了,但还没排好。
第 5 步:直到什么都不动
- 用
repeat until <(swapped) = (0)>把整轮包起来。 - 每一轮开始时把
swapped设成 0,在交换里面设成 1。 - 数一数做了几轮、换了几次,最后说出来。
set [swapped v] to (1)
repeat until <(swapped) = (0)>
set [swapped v] to (0)
change [passes v] by (1)
set [i v] to (1)
repeat ((length of [powers v]) - (1))
if <(item (i) of [powers v]) < (item ((i) + (1)) of [powers v])> then
set [hold name v] to (item (i) of [names v]) // and the other eight swap blocks
set [hold power v] to (item (i) of [powers v])
set [hold pic v] to (item (i) of [pics v])
set [swapped v] to (1)
change [swaps v] by (1)
wait (0.3) seconds
end
change [i v] by (1)
end
end
say (join [Sorted in ] (join (passes) [ passes.])) for (3) seconds
怎么用: 点绿旗,看两个列表框。牌一次移动一行,直到什么都不动。
两行最后变成了同一张牌。
少了一个 hold,或者有一个 hold 放在了 replace 后面。先做完三个 hold,再做三次抄上去,最后做三次放下来。
力量排好了,名字却乱了。
交换只动了一个或两个列表。每一次,三个列表都必须一起动。
它永远停不下来。
一轮的最上面少了 set [swapped v] to (0),所以它永远是 1。每一轮开始时都把它设成 0。只有真的换了,才把它设成 1。
最后一张牌总是排不好。
一轮重复了整个长度,而不是长度减 1。或者重复了长度减 2。数一数六张牌的牌组里有几对。答案是五对。
它一下子就做完了,我什么都看不到。
交换里面少了 wait (0.3) seconds。
故意弄坏它
把你的排序复制一份。删掉交换名字和图片的积木,只让力量动。运行它,看看会发生什么。
- 力量排得整整齐齐。
- 名字一动不动,还在原来的地方。
- 你能指着一张牌,说出它本来应该是多少。
怎么用: 点绿旗,看力量在排序,名字却站着不动。最后读一读第 2 行。
Teacher note
Deliberately breaking something is a real debugging skill and this is a good first one, because the damage is quiet: nothing errors, nothing stops, the list just lies. Ask how they would have noticed if they had not been told.
弱的在前
改得越少越好,把牌组倒过来。
- 排好后,最弱的牌在最上面。
- 名字和图片还是配着它们的力量。
- 你只改了一块积木。
怎么用: 点绿旗,看小的牌往上走,而不是大的。
Teacher reveal
if <(item (i) of [powers v]) > (item ((i) + (1)) of [powers v])> then
A < became a >. Nothing else. Pupils who rewrote the swap to move things the other way have done a lot of work for the same answer — which is worth noticing out loud, kindly.
这花了多少功夫?
数一数排序花了多少功夫。然后找出什么能让它少做一点。
- 数一数做了几轮、比较了几次、换了几次。
- 先在打乱的牌组上运行,再在差不多排好的牌组上运行。
- 把两组数字都写下来,比一比。
怎么用: 点绿旗。这个牌组只有一张牌放错了位置,看看它要做的事有多少。
Teacher reveal — the shape of the answer
A sorted deck costs one pass: it compares everything, swaps nothing, and stops. A deck sorted backwards is the worst case and needs a pass for every card. That gap — between about n comparisons and about n × n — is the first time a pupil meets the idea that the same algorithm can be cheap or expensive depending on what you feed it. Name it; do not formalise it.
按名字排序
用你已经做好的排序,把牌组按字母顺序排好。
- 比较看的是 names 列表,而不是 powers。
- 三个列表还是一起动。
- 排好后是从 A 到 Z。
怎么用: 点绿旗,看同一个排序把单词排好顺序,而不是数字。
Teacher reveal
if <(item (i) of [names v]) > (item ((i) + (1)) of [names v])> then
One list name changed and one comparison flipped. Everything else — the nine-block swap, the pass, the until — is untouched. That is the payoff of having built an algorithm rather than a script, and it is worth saying so explicitly at the end of the lesson.
总结 5 分钟
- 交换两行,需要第三个框先拿着其中一个。
- 一轮把每一对相邻的牌比一次。最大的会浮到最上面。
- 冒泡排序就是一轮一轮地做,直到有一轮没有交换。
- 一起走的列表要一起交换,不然数据就会错。
- 差不多排好的列表只要做一点点事。倒过来的列表是最坏的情况。它们用的是同一个算法。
- 交换
- 用一个临时的框,把两行对调过来。
- 一轮
- 沿着列表走一趟,比较相邻的两个。
- 冒泡排序
- 一轮一轮重复,直到什么都不动。
- 临时变量
- 一个只用来暂时拿着东西的框。
交作业
保存你排好的牌组。下节课,它会变成一场你能玩的比赛。你刚写的排序会用来管排行榜。