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的排序过程相同，找到合适的位置通过移动、插入的方法完成排序。