插入排序算法

陈新龙

算法是编程考试中最常见的题目。几乎所有的笔试和面试都会考，因为它体现的是程序员的算法基础和逻辑思维能力。经常阅读计算机新闻的读者知道，我们已经讨论了许多种排序算法，如冒泡排序、选择性排序、桶排序...

所以你有没有想过一个问题:为什么排序算法这么多？首先，因为排序的思路是多样的，从不同的角度解决排序问题会导致排序方法的不同。另外，不同的排序算法各有优缺点。当数据大小不同时，可以选择合适的排序算法。

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

今天给大家分享一种新的排序算法“插入排序”。插入排序可分为前插入顺序和后插入顺序。它的基本思想是把数组中的第一个数看作一个有序数组，从后到前或从前到后扫描这个有序数组，将数组中剩余的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之间的随机数添加入原数列列表中（随机数的范围和重复执行的次数可自定义）。

在了解了运行流程和插入排序的思路后，可以尝试用Scratch拼出代码。首先，创建两个新的列表来存储原始序列和排序后的序列。在开始的时候，清除系列空中的所有内容。通过重复执行的方式将1到50之间的随机数添加到原系列的列表中(随机数的范围和重复执行的次数可以自定义)。

其次，创建两个关键变量“进行中”和“已分类”。由于插入排序从第二个项目开始，变量“进行中”表示要插入排序的序列的顺序位置。变量“已排序”是指序列中已排序的序列组从第一项开始，反复执行，直到进程中的项数大于序列中的总项数，这样就可以跳出循环。在循环中，将要处理的数字与排序后的序列中的数字进行比较，通过比较大小将处理后的数字插入到适当的位置。流程中的编号在排序后的序列中排在下一位，流程中的编号随着循环每次递增1，直到循环序列结束，排序结束。

插入排序的好处是稳定性和速度，但是比较的次数不一定。比较次数越少，插入点后移动的数据越多。尤其是当数据总量巨大时，就需要链表来解决这个问题。