插入排序——扑克牌排序

插入排序可以类比我们打扑克牌：我们拿到扑克牌一般都是按照顺序来进行排列(同花顺)。先从左往右进行排列，把后面的插入到前面中。

插入排序原理

插入排序的工作原理：从乱序的数组中依次取值，插入到一个已经排好序的数组中。

这看起来好像需要两个数组才能完成，但是实际上只需要一个数组也可以完成。此时需要想象出两个区域：前方有序区和后方乱序区。

其具体步骤如下：以【1，3，2，5，6】为例。

1. 分区。开始时前方有序区只有一个元素，就是数组的第一个元素，这里就是数字1。然后把从第二个元素开始直到结尾的数组作为乱序区，也就是【3，2，5，6】。
2. 从乱序区中取第一个元素，把它正确插入到前方有序区中。把它与前方有序区的最后一个元素进行比较，也就是与它的前一个元素进行比较。
   如果比前一个元素要大，那么就不需要交换位置，这时有序区往后增加一个，乱序区往后缩减一格。
   如果跟前一个元素相等，那么与前第二个元素进行比较，如果大于前第二个元素，则不需要交换顺序。如果小的话，看下一条。
   如果比前一个元素要小，则交换他们的位置，交换完之后，继续比较取出元素和它此时的前一个元素，若更小就交换，若相等就比较前一个，直到遍历完成。至此，把乱序区第一个元素正确插入到前方有序区中。
   往后缩小乱序区范围，继续取缩小范围后的第一个元素，重复第2步骤。直到范围不能缩小为止，排序完成。

以[1,3,2,5,6]为例:
第一步：首先有序区为[1]，乱序区为[3,2,5,6]

第二步：取出乱序区中的第一个元素3作为比较元素，将其与有序数组的最后一个元素，也就是它的前一个元素1进行比较。3>1.不需要交换顺序，有序区变为[1,3],乱序区变为[2,5,6].

第三步：取出乱序区中的第一个元素2作为比较元素，与有序区的最后一个元素3进行比较，2<3，那么需要交换顺序，变成了[1,2,3]再拿比较元素2，与它前面的1进行比较，2>1不需要交换顺序。

插入排序的实现

插入排序特点

插入排序在比较的过程中可以中断排序，如果值比前面的大，那么就可以直接结束排序。进行下一个值的排序。因此插入排序对于近似有序的数组效率非常高