Scratch选择排序-玩扑克学算法系列之二

什么是选择排序？

选择排序(Selection sort)是一种简单直观的排序算法。其基本思想是：

其排序方式可以参考下图：

选择排序过程

会打扑克就会选择排序，选择排序很像我们打扑克牌时，把牌从左到右扫描，找到最小的一张牌，放到最左边，然后从第二张牌继续扫描第二小的牌，放到第二的位置，以此类推，直至所有的牌都排列好，这个画面感是不是很熟悉，其实这就是选择排序。

为了更好的理解选择排序，下面介绍如何使用扑克牌来演示详细的排序过程。

准备扑克牌一副，红蓝色棋子各一枚，为便于演示，取牌面为2、5、6、7、9的5张纸牌进行排序操作。将5张纸牌打乱顺序，假定牌面从左到右依次为7、9、5、2、6。由于每次都需要挨个比较找到最小的纸牌，因此5张牌需要进行4轮排序。

第1轮排序：将红色和蓝色棋子放在左边第1张纸牌上方，标记为j，然后从红色棋子所在位置的下一张纸牌（j+1）开始，从左至右依次把每一张纸牌与蓝色棋子所在位置的纸牌进行比较，并将蓝色棋子放置在较小的纸牌上方。直到将红色棋子右边的纸牌全部比较一遍，此时蓝色棋子就停留在最小的纸牌上方。然后将红色棋子和蓝色棋子所在位置的两张纸牌交换位置，至此完成第一轮排序，最小的一张纸牌2被移到正确位置，如图：

第2轮排序：将红色棋子和蓝色棋子放置于左边第2张纸牌上方（j=2），按照上述步骤进行比较，然后交换位置，在第二轮排序完成之后，纸牌5就移到了正确位置，如图：

第3轮排序：再将红色和蓝色两枚棋子置于左边第3张纸牌上方（j=3），重复上述过程，对纸牌进行比较和交换，完成第三轮排序后，纸牌6就移到了正确位置，如图：

第4轮排序：继续移动棋子，将它们放到左边第4张纸牌上方（j=4），继续前面的步骤，在第四轮排序完成之后，纸牌7就处于正确的位置，而剩下的纸牌9自然而然也就处于正确位置了，如图：

至此，整个排序过程结束，这是5张扑克牌已经按照从小到大排好序了，依次为2，5，6，7，9。

编程思路

根据上述过程分析，在排序过程中，这里的红色棋子和蓝色棋子是用来进行标记的，可以使用变量来表示，而每一轮排序都需要交换位置，因此需要定义一个自制积木来实现数字的交换。

代码实现

1.创建并初始化列表

建立一个“纸牌”列表，清空列表，并将纸牌数字7、9、5、2、6依次加入列表，编写代码如下：

2.定义“交换元素”自制积木

创建自制积木，用于对列表中的数据进行交换，需要定义两个参数，不过参数不是纸牌本身，而是纸牌对应的编号，编写程序如下：

3.创建“选择排序”自制积木

再建立一个自制积木用于排序，根据上面的排序过程描述，在排序过程中需要设置两个标记，这个可以使用变量来实现，建立两个变量“a”和“b”，同时还需要单独再再利用循环进行多轮排序，具体的代码如下：

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

接下来，就可以调用自制积木进行排序了，如图：

程序效果

程序执行的效果如下：