排序算法：插入排序

微信搜索【程序员囧辉】，关注这个坚持分享技术干货的程序员。

前言

上一次，我们介绍了排序算法中“龟速三兄弟”的大哥“冒泡排序”。今天，我们继续介绍“龟速三兄弟”中的二哥——“插入排序”。“冒泡排序”的过程和代码相信大多数人都比较熟悉，但是“插入排序”就不见得了。由于同样是“龟速三兄弟”中的一员，但是处理过程没有“冒泡排序”那么简单明了，因此有不少人可能都没接触过“插入排序”，本文将通过例子来介绍“插入排序”的完整过程。

基本思想

将一个数插入一个已经排好序的数据中。

1. 第一次循环时，从第2个数开始处理。我们将第1个数作为已经排好序的数据：当第2个数 > 第1个数时，将第2个数放在第1个数后面一个位置；否则，将第2个数放在第1个数前面。此时，前两个数形成了一个有序的数据。
2. 第二次循环时，我们处理第3个数。此时，前两个数形成了一个有序的数据：首先比较第3个数和第2个数，当第3个数 > 第2个数时，将第3个数放在第2个数后面一个位置并结束此次循环；否则，再和第1个数比较。如果第3个数 > 第1个数，则将第3个数插入第1个数和第2个数中间；否则，第3个数 < 第1个数，则将第3个数放在第1个数前面。此时，前三个数形成了一个有序的数据。
3. 后续的数据同理处理，直至结束。

例子

下面通过一个例子来看看插入排序是怎么工作的。原数组如下。

第一次循环：

1.从第2个数开始处理，即array[1]。比较array[1]和arary[0]，即15和19。因为15 < 19，所以将arary[1]放在array[0]的前面，放完后的数组如下。