趣学妙用Scratch编程48 进阶篇（十八） 谁才是排序冠军？

Scratch世界第一届排序比赛开始了，下面有请各位选手出场！他们依次是——冒泡排序、选择排序、插入排序、快速排序……

开个玩笑，其实我们学的排序算法才四种而已，经典的排序算法至少就有十种以上，我们学的还远远不够呢，但这不影响我们对已经学到的排序算法进行一下分析比较，顺便再总结一下排序算法：

问题

用同一组生成的随机数据去验证四种排序算法（冒泡、选择、插入、快速）的性能，看看在相同的数据上它们各自用了多长时间完成排序。要求： - 数据随机生成，但要允许指定随机生成的数量，比如1000，100000等； - 生成的数据复制分别用于不同的排序，不能用已经排序好的数据去让另一个算法排； - 将最终的使用时间加入列表中显示。

分析

我们在前四节的课程中，已经把各种排序算法都实现成自制积木了，现在要考虑的关键问题有： - 为了公平起见，需要用同样的数据给不同的排序算法运算。如果每次随机生成数据，可能数据的前后次序是不一样的，而且一旦完成排序，再让另一种算法拿这个排好序的列表去排也不合适。因此，我们会建立两个列表，一个用于保存随机生成数据的随机列表，不会改变；另一个是所有排序算法的比赛场地，称为工作列表。比赛开始后，我们先清空并随机生成数据保存到随机列表。在每一种排序算法开始工作之前，我们把工作列表清空，把随机列表的数据全部复制到工作列表当中去。一种算法完成工作之后，我们再把工作列表清空，把随机列表数据复制过来用。这样就解决了公平性问题。 - 为了保存各种排序算法的成绩，我们建立新的列表“排序纪录”，在每个排序算法开始工作时，计时器清零，然后在这个算法完成工作后，把它使用的时候保存到排序纪录中。 - 原有的排序算法自制积木都复制过来供调用。

编程

一、编写代码完成数据初始化、数据刷新的过程。原有的关于排序的自制积木请参考前几节的代码，这里不再列出。  

  二、我们可以分别用10、100、1000来测试四种算法的排序性能了：  

  10个数据排序的用时居然大家都是0！这是因为数据少，运算太快了，Scratch的时钟还来不及对它进行计时，所以我们看不出大家排序谁快谁慢；  

  100个数据，嗯，这次有点差别了，前面几个不到一秒种，差别不太大，而快速排序还是0，说明只有快速排序快到了来不及计时的程度。我们继续：  

  1000个数据排序，这次差异就很明显了，我们看到冒泡最慢，用了5秒，选择和插入差不多2-3秒。当然，这可能和随机数据的顺序有关，它们总体还是一个量级的，而快速排序呢？人家还是遥遥领先啊！居然不到0.2秒！再继续——  

  这次就更加明显了，我们不能断定前几个谁更快，因为有数据因素，但是谁是这次排序比赛的冠军已经很明显了，它就是——Quicksort（快速排序）！  

  如果同学们有兴趣，还可以用更多的数据去进行试验，这里我就不一一展示了。但是要注意，千万不要输入1000000这类看上去不长的元素数，每多一个0，计算机要做的工作就多了一个数量级，我们用的都不是超级计算机，如果排序时间太长，你会没有耐心等下去。 [video width="848" height="634" mp4="https://cdn.scratch5.com/wp-content/uploads/2023/07/1eb5cdb0-c937-11ec-ba65-fed26b50d866-v4_t10000111-wfbbBF7WeG.mp4"][/video]

总结

终于，我们完成了排序算法的学习，而Scratch进阶篇的内容，也就差不多完成了。我们对排序算法做个简单的总结吧：

• 冒泡排序：它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序与要求的排序不符合就把它们交换过来。每走一轮，都有一个元素排序到位，所有元素找到位置，排序结束；
• 选择排序：从未排序的数据中找出一个最小或最大的放到“已排序”部分的起始位置，再从剩下的未排序列表中继续寻找最小或最大的元素放到已排序数据的末尾，重复直至所有元素完成排序；
• 插入排序：把列表分成已排序和末排序两部分，开始时把第一个元素认为是已经排好序的，从第二个元素开始，在已经排序好的数据中寻找合适的位置插入，直至所有元素被插入到有序列表中；
• 快速排序：我们的目前掌握的排序冠军，它的方法是从列表中挑出一个元素作为基准，重新排序使所有比基准小的元素放在基准前面，所有比基准大的元素放在基准后面（相同的数则可以放在任何一边），分区结束后，这个基准就处于正确的位置了，再把它左边的区间和右边的区间按照上述方法递归进行快速排序，直至分区不能再分为止（也可能为空）。

在我们学到的四种算法中，随着待排序元素的增加，不同的排序算法用的时间不一样，其中快速排序和其它三种不是一个量级的。这反映的是当要解决问题规模增大的时候，排序时间变化的趋势，我们将来会学习排序算法的时间复杂度。现在我们只需要知道——快速排序是真的快！