插入排序的思路
插入排序是简单排序中效率最好的一种.插入排序也是学习其他高级排序的基础，比如希尔排序/快速排序，所以也非常重要.
局部有序
插入排序思想的核心是局部有序。什么是局部有序呢？
比如在一个队列中，我们选择其中一个作为标记的队员.这个被标记的队员左边的所有队员已经是局部有序的.这意味着，有一部分人是按照顺序排列好的，有一部分还没有顺序.
插入排序的思路
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一个位置
4、重复上一个步骤，直到找到已排序的元素小于或等于新元素的位置
5、将新元素插入到该位置后，重复上面的步骤
插入排序的效率
插入排序比较次数
第一次时，最多需要1次，第二次最多是2，依次类推，最后依次是n-1次
因此插入排序的最多次数：1+2+3+…+(n-1) = n * (n - 1) / 2
然而每次发现插入之前，平均只有全体数据项的一半需要进行比较.我们可以除以2得到n*(n-1)/4，所以相对于选择排序，比较次数是少了一半的
插入排序的复制次数
第一次，需要的最多复制次数是1，第二次最多是2，。。。最后一次n-1。因此复制次数最多是1+2+3+…+(n-1) = n * (n - 1) / 2.平均次数n * (n-1)/4
对于基本有序的情况
对于已经有序或基本有序的数据来说，插入排序要好很多
当需要有序是，while循环的条件总为假，所以它变成外层循环中的一个简单语句，执行n-1次
在这种情况下，算法运行只需要O(N)的时间，效率相对来说会更高
另外别忘了，我们的比较次数是选择排序的一半，所以这个算法的效率是高于选择排序的