Scratch插入排序算法

陈新龙

排序算法是编程考试中最常见的题目，几乎所有的笔试和面试都会考到，因为它体现的就是程序员的算法基础和逻辑思维能力，经常看《电脑报》的读者们都知道，我们已经讲了多种排序算法比如冒泡排序、选择排序、桶排序……

那么大家有没有思考一个问题：为什么有那么多种的排序算法呢？首先是因为排序的思路是具有多样性的，从不同的角度解决排序问题，就会产生不同的排序方法。另外，不同的排序算法各有优势和劣势，当数据规模不同时，可以选择合适的排序算法。

今天就和大家分享一个新的排序算法“插入排序”，插入排序分为前插序和后插序，它的基本思想是将数组的第一个数认为是有序数组，从后往前或者从前往后扫描该有序数组，把数组中剩余n-1个数，根据数值大小，有序插入到前面序列中，直至数组所有数有序排列为止。这样的话，n个元素只需要进行n-1趟排序，比多数排序算法的效率更高。

例如有一组数列为【53、27、36、15、69、42】。首先对于待排序数组中第一个元素53认定为有序元素，所以排序从第二个元素27开始。第一次排序时从有序数列中查找27插入的位置。27小于53应插入在53之前，此时将27提取出来后，将53后移，将27放入原53点位置，便完成了第一次排序。

第二次排序的时候从有序序列中找36的插入位置。36小于53，大于27，36的插入位置在27与53之间。此时将36提取出来后，将53后移，再将36放入原53所在位置，便完成了第二次的排序。

剩余的数字15、69、42的排序过程相同，找到合适的位置通过移动、插入的方法完成排序。最终的排序数列结果为【15、27、36、42、53、69】总计五次排序。

了解了插入排序的运行过程和思路后，我们可以尝试着用Scratch将代码拼搭出来。首先新建两个列表用于存放原始数列和排序后的数列，开始时将序列中所有的内容全部清空。通过重复执行的方法，将1-50之间的随机数添加入原数列列表中（随机数的范围和重复执行的次数可自定义）。

其次新建 “处理中”和“已排序”两个关键变量。由于插入排序是从第二项开始，所以变量“处理中”表示需要插入排序的数列的序列位置。變量“已排序”代表数列中已经完成排序的数列组从第一项开始的，一直重复执行直到处理中的项数大于数列项数的总和便可跳出循环。在循环中，将需要处理的数和已排序数列中的数字进行比较大小，通过比较大小将处理中的数字插入到合适的位置。处理中的数排在已排序数列的下一个数字，同时处理中的数字跟随着循环每次加一，直至循环数列末尾，排序结束。

插入排序的优点就是稳定，速度快，但是比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，需要用链表解决这个问题。