28.排序问题

本章我们尝试用Scratch来给一个无序的列表排序。如果你已经完成了贪吃蛇的游戏，那么你对列表应该已经有一定了解了。现在我们先要新建一个列表“list”，如图28-1所示。

图28-1 新建列表“list”此时，这个列表是空的，接着就需要利用随机数创建一个无序的列表，这里设定列表中数据的长度（数量）为10。对应的程序如图28-2所示。

图28-2 创建无序列表的程序我希望这些数之间的差距大一些，所以随机数的范围选择的是1~100。这段程序是通过空格键触发的，当我们按下空格键时，就能看到列表中生成了10个无序排列的数。每个数前面都有一个对应的编号，表明数据在列表中的具体位置。这10个数生成之后，生成列表数据的这段程序就可以删掉了。下面我们就来通过程序为“list”中的数排序。排序前，我们需要再新建一个列表“list2”以及一个变量“var”，如图28-3所示。之所以这么麻烦，主要是因为列表不像数组那样可以直接访问其中的任何一位数据。

图28-3 新建列表及变量排序的方式采用的是冒泡法，冒泡法的一个循环的具体操作如下。（1）将“list”中的第一个数放入变量“var”中，同时删掉“list”中的第一个数，此时“list”中就只有9个数了，即原来的第2个到第10个。（2）用现在“list”中的第一个数和变量“var”的值进行比较，如果这个数比“var”的值小，那就把这个数直接放到“list2”中；如果这个数比“var”的值大，那就把“var”的值放入“list2”，并把现在“list”中的第一个数放在“var”中，同时删掉“list”中的第一个数。（3）再重复第二步操作8次。因为我们会不断地用“list”中的第一个数和“var”的值进行比较，这样“var”中保存的就始终是最大的数。8次（再加上第二步中的1次）之后，“var”中保存的就是整个10个数中最大的数，这个过程就好像冒泡一样，所以这种排序的方法称为冒泡排序。（4）为了重复以上的操作，将“list2”整个复制到“list”。同时将“var”的值放在“list”中的最后，此时相对于之前的“list”来说就已经选出的最大的数。（5）重复（1）到（4）步10次，这样整个列表就按照从小到大的顺序重新排序了（有可能少于10次，10次只是最坏的情况）。下面我们来实际操作。第（1）步对应的程序如图28-4所示。这里为了便于操作，我为每一段程序都添加了一个快捷按键，按下相应的按键就能执行对应的程序。第一步的快捷键是a。

图28-4 快速键a的程序当按下键盘上的a键时，注意变量和列表的变化，此时列表“list”中的第一个数就给了变量“var”。第（2）步对应的程序如图28-5所示，对应的快捷键是b。当按下键盘上的b键时，由于此时“list”中的第一个数是56，这个值比“var”中的值小，所以，要将56加到“list2”中。

图28-5 快捷键b的程序接着就是重复操作了。由于我们设定了快捷键，只需要按下快捷键即可。在重复8次之后，除了“var”中的数，其他9个数都已经移动到“list2”中了。运行效果如图28-6所示。

图28-6 程序运行效果此时就到了前面说的第（4）步了，要将“list2”整个复制到“list”当中，同时将“var”的值加到“list”中，具体的程序如图28-7所示，对应的快捷键是c。

图28-7 快捷键c的程序然后就是要重复前面的所有操作了，一个过程中快捷键a的程序执行1次，快捷键b的程序执行9次，最后快捷键c的程序执行1次。然后就能选出最大的两个数了。下面我们将几段程序组合起来用一个快捷键控制，如图28-8所示，这里在原来快捷键b的程序外面加了一个“重复执行9次”的指令模块。合成后的程序快捷键是a。此时按下这个快捷键，就会直接选出第三大的数。这样我们就知道，如果再重复目前的整个程序6次（最后一次不用排了），我们就能将整个列表按照从小到大的顺序排列了。由此，我们在整个程序外面加一个9次的循环，就是一个完整的10个无序数据的排序方法了。再进一步地设定一个变量“lengthOfList”来表示列表的长度，并用这个变量代替指令模块中的数字9，这样就完成了一个通用的列表排序程序，如图28-9所示。目前这个程序的快捷键依然是a。

图28-8 组合程序  

图28-9 添加变量“lengthOfList”