Scratch插入排序-玩扑克学算法系列之三

什么是插入排序？

插入排序是一种简单的排序算法，也称之为直接插入排序，它的基本思想是：

其过程如图所示：

插入排序很像大部分人玩扑克牌时的操作，从第二张牌开始,跟第一张牌比较， 如果比第一张牌小，那么就插入到第一张前面，这样两张牌就是排好序的，然后再把第三张牌跟前面排好序的两张牌做比较，插入到已经排好序的两张牌里面，这样就形成了三张排好序的牌,，后面的牌一次就行插入排序操作。这种打牌排序方式才是大多数的选择，前面选择排序的方式可能只有极小部分与众不同的人会那么操作。

插入排序过程详解

下面介绍如何使用扑克牌演示插入排序算法，准备扑克牌一副，红、蓝色棋子各一枚，为便于演示，取牌面为2、4、6、7、8的5张纸牌进行排序操作。将5张纸牌打乱顺序，假定5张牌从左到右一次为6、4、8、2、7。

先把左边的第1张纸牌翻开，作为已排序部分，其他纸牌作为未排序部分。对于5张牌，我们需要使用经过4轮排序。

第一轮排序：将红色棋子（标记为j）和蓝色棋子（标记为i）放在第2张纸牌处，再将纸牌4与左边的纸牌6进行比较，将较小的纸牌4与纸牌6交换位置，将蓝色棋子向左移动一步，这是i=1，结束第一轮排序，纸牌4处于正确位置，如图：

第二轮排序：将红色和蓝色棋子右移一步放在第3张纸牌上方（j = j + 1），再将纸牌8与左边的纸牌6比较大小，它比纸牌6大而无需交换，结束第2轮排序，纸牌8处于正确位置，如图：

第三轮排序：将红色和蓝色棋子右移一步，放在第4张纸牌上方（j = j + 1），再将纸牌2与左边的纸牌8进行比较，将较小的纸牌2与纸牌8交换位置，将蓝色棋子左移一步，再与纸牌6比较大小，交换位置，继续左移蓝色棋子，与纸牌4进行比较，需要交换位置，左移蓝色棋子，此时已经到左边了，结束第三轮排序，纸牌2已经处于正确位置了，如图：

第四轮排序：将红色和蓝色棋子右移一步放置于第5张纸牌上面（j = j + 1），再将纸牌7与左边的纸牌8比较大小，将较小的纸牌7与纸牌8交换位置，左移蓝色棋子，将纸牌7余纸牌6比较大小，它比纸牌6大无需交换，这时结束第四轮排序，纸牌7已处于正确的位置上了，如图：

至此，整个排序过程结束，这时5张扑克牌已经按照从小到大的顺序排列完毕。

编程思路

根据上面的过程描述，首先需要定义一个交换两个数组元素的自制积木，用于交换纸牌，然后就可以调用自制积木来进行排序了，排序的时候，从第2个元素开始处理，每一轮只处理一个元素，把当前需要的处理插入到正确位置即可。

程序实现

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

建立自制积木，命名为交换元素，需要两个参数a和b，表示列表元素的下标，temp则是临时保存数据的变量，代码如下：

2. 定义“插入排序”自制积木

接下来，再建立一个自制积木，命名为“插入排序”，再结合双重循环，完成排序，对应的代码如下：

3. 对纸牌进行插入排序

仍然遵循IPO的设计原则，先输入数据，调用自制积木进行处理，然后输出结果，编写代码如下：

作品效果

运行程序，其完整的效果如图所示：