Scratch快速排序-玩扑克学算法系列之五

什么是快速排序

快速排序是对冒泡排序的一种改进，它是由东尼·霍尔在1962年提出的一种划分交换排序，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数，快速排序被认为是当前最优秀的一种内部排序算法，它的基本思想是：

快速排序过程详解

为了让你更好的理解快速排序，下面将介绍如何使用扑克牌来演示快速排序算法。

准备好扑克牌一副，红、蓝色棋子各一枚，为便于演示，取牌面为2、4、6、7、8的5张纸牌进行排序操作。将5张纸牌顺序打乱，假定5张牌从左到右依次为7、6、8、2、4。

第一轮排序：开始时5张纸牌都未排序，在左右两端的第1张牌和第5张牌上方各放置一枚红色和蓝色棋子，以红色棋子出的第一张纸牌7作为基准，然后先从右到左移动蓝色棋子，将它停留在找到的第一张小于基准的纸牌4上方；再从左向右移动红色棋子，将它停留在找到的第一张大于基准牌的纸牌8上方。这时红蓝两枚棋子没有碰到一起，将它们下方的两张纸牌8和4交换位置。

按这个方法继续移动蓝色和红色棋子，它们都停留在纸牌2的上方，这时两枚棋子碰到一起，将纸牌2和7交换位置，至此，基准纸牌7就移到了正确的位置，而整个未排序的纸牌被基准纸牌7划分为两个未排序的分区，排序过程如图所示：

第二轮排序：在第1张和第3张纸牌上方分别各放置红色和蓝色棋子，将第1张纸牌2作为基准，然后按照上面描述的方法移动两个棋子，它们都停留在纸牌2的上方。这时基准牌位置和两枚棋子相遇的位置相同，不需要处理，基准纸牌2已经处于正确位置，如图所示：

第三轮排序：在第2张第3张纸牌上方分别放置红色和蓝色棋子，将第2张纸牌6作为基准，然后按照前面描述的方法移动两枚棋子，它们相遇在纸牌4上方，这时将纸牌6和纸牌4交换位置，至此，基准纸牌6就被移到了正确的位置，如图：

最后就剩下第2张和第5张纸牌这两个未排序的分区，由于这两个分区都只有一张纸牌，不需要继续分区，因此它们已经处于正确位置了，因此，整个快速排序过程也就结束了，5张纸牌已经按照从小到大的顺序排列好了。

编程思路

根据快速排序的基本思想，对于一个未排序数组，每一轮排序都需要先确定基准点，并寻找分区点，在寻找分区点的过程中，需要将右侧小于基准点的数字和左侧大于基准点的纸牌进行交换，一旦找到分区点，则将基准点的纸牌和分区点的纸牌进行交换，然后分别对左边和右边的分区重复这个过程即可。

因此，我们需要依次解决如下3个问题：

• 交换指定位置的纸牌
• 寻找分区点
• 递归调用

程序实现

1.定义“交换位置”自制积木

根据编程思路的分析，先来解决第一个问题，即交换指定位置的纸牌，可以定义第一个自制积木，如下：

2.定义“寻找分区点”自制积木

接着，就可以定义“寻找分区点”自制积木了， 代码如下：

3.定义“快速排序”自制积木

由于需要用到递归，这里必须要定义一个“快速排序”自制积木，然后在自制积木中再次调用自己，具体的代码如图所示：

4.调用自制积木完成快速排序

有了快速排序自制积木，就可以直接对纸牌数组进行排序了，在绿旗指令下添加代码如下：

作品效果

Scratch快速排序的执行效果如下图所示：