趣学妙用Scratch编程27 妙用篇（十五） 来给列表排个序

知：关于排序那些事儿

我们已经做了不少实用性的小工具，本节我们来聊点“抽象”，但又是一名专业的软件工程师必须熟悉的概念——“排序”。 开始之前，先来向你推荐一本书，准确地说是一套书，它的名字叫《计算机程序设计艺术》，这套书是所有专业程序员书架上的“圣经”。它有多厉害呢？微软前董事长比尔盖茨曾经对全世界说过—— “如果你完完整整读完了《计算机程序设计艺术》，请立刻给我发一份简历。” 也就是说，你读懂了这套书，直接就可以到世界上最大的软件公司之一去面试了！ 当然，这套书可不是推荐你现在读的，我只是希望你记住这套书的名字，等到有朝一日机缘成熟的时候去翻开它。那么这套书和我们所说的“排序”有什么关系呢？《计算机程序设计艺术》第三卷就叫“排序与查找（Sorting and Searching）”，现在你知道排序对于掌握编程技能提升有多重要了吧？我们先不必过分深入地学习概念，而是结合具体问题，直观地体会一下排序的执行过程：

老师给小猫出了一道题，要求在列表 1 中生成 5 个在 1~ 99 范围内 的随机整数，列表2为空，小猫说“5秒钟后开始排序”，然后将列表1中的数字按照从大到小的顺序依次移到列表 2 中（注意是移动，不是复制），然后说“处理完啦”，程序结束。例如：在列表 1 中随机生成的整数依次是 12,3,1,13,17，在处理之后列表 2 中的整数依次是17,13,12,3,1。

思：程序设计

经过简短的思考你就会发现，这道题目其它都不难，主要解决的问题就是怎么从列表1中每次找出最大的数字，然后把这个数字添加到列表2，再删除这个最大项。这样重复5次，就能将所有数字依次移动到列表2当中去。那么怎么找到列表中最大值？当然得用到重复执行，用一个刚开始设置为0的“最大值”变量与列表中的每一项依次比较，如果列表项比它大，就把这个编号记录下来，并把变量“最大值”设置为当前列表项，再与列表下一次比较。等到列表中所有项都比完了（列表中有多少项，就比较多少次），这个“最大值”变量中保存的就是列表1最大值，我们把它添加到列表2，再根据记录的编号删除掉列表1中的这一项，就实现了移动效果。根据题目要求，重复5次就实现了列表1所有项依次移动到列表2。

行：编程实现

1、新建项目，这次我们的舞台布置很简单，保留空白背景，添加列表1、列表2显示到舞台上，再添加“列表序号”、“最大值”、“最大值序号”三个变量。为了直观，可以将它们也保留在舞台上显示：

2、我们可以使用自制积木，把“移动最大值”这个关键的逻辑先实现出来：

3、有了移动最大值，其它的代码就简单了，生成列表，然后调用五次“移动最大值”，就能够实现题目要求：

4、执行排序，验证一下你的程序运行是否正确？如果你想仔细地体会一下程序运行的过程，可以在自制积木的循环中加入说话指令，就可以看到每比较一次，最大值、最大值编号的变化情况，你对“排序”的概念理解也就更深入啦。

悟：总结与拓展

本题的排序并不复杂，我们进一步思考一下——算法是解决问题的方案，解决特定问题会有许多种算法，设计算法的目的是找出效率最高或者说最优的算法。那么怎么衡量算法优劣呢？一般我们可以用它的总运行时间或者占用的存储空间来衡量。 拿本例来说吧，虽然不同的排序方式执行逻辑不同，但都要进行比较，而每次执行比较的时间基本是一样的，我们只需要看一种算法执行了多少次比较，就可以与其它算法进行比较，比较的次数越少，说明这个算法越高效。我们用的方法执行了多少次比较呢？简单计算一下，外层总共执行了五轮循环，第一轮执行时，列表1中有5个数字，每个数字比较一次，需要比较5次；到第二轮时，列表1中只剩下四项了，所以要比较4次，然后依次是3次、2次、1次——也就是说总共比较了5+4+3+2+1=15次！如果你能设计出其它的方式，可以用同样的方法来计算一下执行效率。 要了解更多关于排序的知识，不妨在网络上搜索一下“常见的排序算法”——你会找到冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序等一大堆算法，具体它们的特性，就有待于你在日后的编程生涯中进一步学习掌握啦！