蓝桥杯青少年创意编程大赛Scratch编程题解析（五）

列表排序

1.问题描述

老师给小猫出了一道题：在列表1中生成5个在1～99范围内的随机整数，然后按照从大到小的顺序将它们依次移到列表2中。

例如：在列表1中随机生成的整数依次是“12，3，1，13，17”，在处理之后列表2中的整数依次是“17，13，12，3，1”。如图1、2。

具体要求：（1）每次点击绿旗后，在屏幕中都显示如图1所示的列表1和列表2，且在列表1中随机生成5个在1～99范围内的随机整数，而列表2中内容为空。然后小猫说“5秒钟后开始处理”，并等待5秒钟。

（2）处理数据时，每间隔1秒钟，都将列表1中当前最大的一个数字移动到列表2中，注意：是移动，不是复制。

（3）当处理到列表1为空后，列表2中的数据应从大到小排列，如图2所示，然后小猫说“处理完啦”2秒钟，然后程序结束。

评判标准：10分，点击绿旗后，在列表1中正确生成了5个随机的整数（裁判可多次点击绿旗来验证是否随机），且小猫说“5秒钟后开始处理”，并等待5秒钟。

30分，在10分标准的基础上，开始处理后，每1秒钟都将列表1中当前最大的数字移动到列表2中，但不是每次都移动最大数字或者移动到列表2中后顺序不是从大到小，或者处理完成后小猫没有说“处理完啦”，2秒钟。

50分：完全符合题意。

2.编程思路

（1）随机生成5个数字并存入列表1。

（2）找到當前列表1中的最大的数并存储到列表2中，然后删掉这个数，完成移动。

（3）重复执行第2步，直到列表1为空，结束循环。

（4）本题的难点是找到列表中最大的数。对列表排序的算法有很多种，本题数据量非常少，任何一种排序算法都是可以的。学习编程的小朋友可能都接触过相对简单的“冒泡排序算法”。标准的冒泡法是针对一个列表内排序，本题是两个列表，需要做针对性的修改。

3.冒泡排序算法

我们来看看原版的算法步骤，这个步骤由于和题目要求有差异，只能借用，不能直接套用。

（1）需要降序排列，让第一个数最大，最后一个数最小。

（2）比较相邻的元素。如果第一个比第二个小，就交换它们两个，保证大的数更靠前。

（3）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这样最后的元素应该会是最小的数。

（4）针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

4.本题算法

冒泡法的核心是依次比较相邻两个数，并根据情况决定是否交换位置。

例如本题的列表“12，3，1，13，17”，建立一个“临时”变量记录列表的第一个数12，建立一个“临时序号”记录数据的序号1。依次与后面的数据比较，遇到3、1就不变，遇到13时“临时”就替换为13，“临时序号”变为4。一直对比到列表的末尾，这时“临时”变量中记录为17是列表1中最大的数值，“临时序号”为5。这时将数据17放入列表2的第一个位置，并删除列表中序号5的对应数值17。依次循环直到列表1中没有数据为止。

算法流程图如图3。

5.编程实现

（1）对小猫编程，建立列表1、列表2。建立变量临时、序号、临时序号。清空列表。

（2）重复5次，将随机数加入表1。如图4。

（3）重复执行直到表1项目数为O。将序号、临时序号设为1，将临时设定为表1第1项。

（4）重复执行表1项目数-1次。如果表1（序号+1）项>临时，将临时替换为（序号+1）项，记录临时序号为（序号+1），将序号增加1。否则将序号增加1。此步骤完成时，临时保存表1最大数，临时序号记录着它在表1的位置。

（5）将临时加入表2，删除表1的临时序号项。根据题目要求等待1秒。

（6）说“处理完啦”2秒。程序如图5。

6.解题思路B

本例中排序使用了临时变量来存储当前最大的数。下面提供另外一种解题思路，只使用2个变量，序号和最大项序号。比较第1项和第2项，如果第2项大于第1项，则将第2项作为最大项序号。接下来比较第2项和第3项，如果第2项大于第3项，则将序号加1，第2项继续与第4项比较。比较到列表最后将最大项序号对应的值拷贝到表2中，并删除。具体程序如图6。