Scratch之插入 排序算法

在编程中我们经常会用到排序，排序的目的是将一组“无序”的数列调整为“有序”的数列。

之前我们已经通过解题接触到了冒泡排序和选择排序（参见2020年7期《蓝桥杯青少年创意编程大赛 Scratch编程题解析（五）》）。

冒泡排序的思路是：比较相邻的两个数据，如果第二个数据比第一个数据小，交换位置，一直重复比较的操作，从开始的第一对到结尾的最后一对，比较结束之后，最后的元素是最大的数字，第一位是最小的元素。

选择排序的思路是：第一次从全部的数列中找出最大或者是最小的数字放在序列的起始位置，然后再次从剩下未排序的数列中寻找最大或最小的数字，依次寻找，直到待排序的数据个数为零。

很多同学就会问排序只有这两种方法吗？当然不是，常用的排序算法就有十多种呢，希尔排序、归并排序、基数排序……今天我们就来讲一种比选择排序和冒泡排序还要简单的排序算法——插入排序。

插入排序是所有排序中最简单的排序方法，它的思路是将一个记录插入到已经排列好的序列表中，从而产生一个新的、记录数增加1的有序表，我们可以看看图中的排序过程（如图1）。

今天我们用Scratch来完成插入排序的代码，首先我们给一组数列中插入5个数字，组成有序的数列。随后随机产生一个数字，比较数字大小，并将数字插入到有序的数列中组成新的有序数列。本例只为数列添加了一个新的数字，主要是为了体会算法思想，你需要根据实际情况灵活运用。

我们将数字2，3，5，7，9有次序地插入到数列之中，这个数列目前是有序排列的。生成一个随机数用来进行插入。下面的算法就是如何把这个随机数插入到这个有序的数列中的合适位置。

首先我们要判断产生随机数是否大于数列最后一位数字9，如果大于数字9的话，要加入到列表的最后一项，因为向列表末位添加数是不能通过插入来实现的。

处理完新数字是最后一项的情况后，我们需要考虑插入的情况了。重复执行，依次比较大小，如果比当前数小，记录当前是第几项，把新数字插入在这个位置前。

因此我们需要把列表中的数據全部循环一次，在循环的过程中，新数和数列中的每一项数字进行比较，如果数列中的某一项数大于随机数，那么将随机数插入到这一项前面，并且停止所有的脚本，每次比对后，都需要对项数进行加1，这样才能依次比较（如图2）。

总结：插入排序是最简单的排序算法，每次处理就是取无序的数列中第一个元素与有序数列的元素从后到前比较，找到插入位置，将该元素插入到有序数列的适当位置上，由于这种算法没有改变原数列中相同大小元素的相对位置，因此称之为稳定排序算法。