scratch3编程学算法:快速排序和桶排序

大家知道，排序是算法的重要内容。算法就是计算或者解决问题的步骤。就像要想做出特定的料理，就要遵循食谱上的步骤；同理，要想用计算机解决特定的问题，就要遵循算法。这里所说的特定问题多种多样，比如“将随意排列的数字按从小到大的顺序重新排列”等等。算法有优劣之分，就以排序为例，我们来看最糟糕的算法与较好的算法之间的差距吧。

使用全排列算法进行排序，① 生成一个由n个数字构成的数列（不和前面生成的数列重复）；② 如果①中生成的数列按从小到大的顺序排列，就结束将其输出，否则回到步骤①。全排列算法是最容易想出来的算法，它列出了所有的排列方法，所以不管输入如何，都可以得到正确的结果。那么，需要等多久才能出结果呢？若运气好，也许第一个就能出现正确排列的结果，然而，实际情况往往并不如我们所愿。也许最差的情况，直到最后一步才出现正确排列，这样，计算机就不得不确认所有可能的排列了。

学过排列组合就知道n 个数字有n! （n! = n(n - 1)(n - 2)…3·2·1）种不同的排列方法。现在，我们来看看仅仅是n = 50时是怎样一种情况吧。① 50! ＝50·49·48…3·2·1，② 50·49·48…3·2·1＞ 50·49·48…13·12·11，③ 50·49·48…13·12·11 ＞10^（40），假设1台高性能计算机1秒能检查1 万亿（ = 10^(12 )）个数列，那么检查10^(40 ) 个数列将花费的时间为10^(40 )÷10^(12 ) = 10^(28 )秒。1 年为31 536 000 秒，不到10^(8 )秒。因此，10^(28 ) 秒＞ 10^(20 ) 年。从大爆炸开始，宇宙已经经历了约137 亿年，即便如此也少于10^(11 ) 年。也就是说，仅仅是对50个数字进行排序，若使用全排列算法，高能计算机就算花费宇宙年龄的10^(9 )倍时间也得不出答案。 然而后面可以看到，较好的算法，即使排1000个数字，用时竟然不足一秒！下面用scratch3图形化编程来实现一下。

1.用递归的思想实现快速排序：思路是将列表首元素放进一个变量，通过比较，将比它小的元素放到它左边，比它大的的元素放到它右边，然后将同样的方法递归地用于被它分开的左右两个子列表，一直做下去。代码（积木）截图如下：

2.以快速排序法为辅助，实现桶排序。桶排序 (Bucket sort)的工作的原理比较简单：假设输入数据服从均匀分布，将数据按一定规则分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。下面以考试成绩表分数（0~100）排序为例，以10分为一段，分成11个桶，然后用快速排序法对每个分数段的桶列表排序，依次放入顺序列表里面。

由于scratch没有二维列表，笔者根据分数段长度和成绩表长度，构建了一个初始值全为空的“桶阵长列表”，将不同分数段的分数放到“桶阵长列表”的不同位置（11个长度为成绩表长度的桶分段），然后将每个桶分段中非空的元素组成一个供排序的“桶表”，用前面的快速排序法对这个“桶表”排序后，依次放入顺序表。代码截图（自制积木“排序列表”与上面相同故略去）如下：