算法-排序之插入排序
插入排序是一种简单的排序算法，这是一种从小范围到大范围的递归思想,这种思想类似于数学推导中的递归，首先在最小规模n（1个数的队列）满足要求，再考虑n+1时需要的操作，递归直到最终的结果。当问题规模很大无从下手时，在问题最小规模点思考，然后逐渐递加，不失为一个很好的选择。
1.插入排序InsertSort
核心：以一个人为初始序列，从第二个人开始每次将一个人插入该队列中
明白了插入排序的核心，你能轻易理解插入排序的步骤：
1.将第一个数作为起始序列
2.将下一个数插入序列，
3.直到所有数全部插入序列，得到完整有序结果
以3为起始序列，分成如下
将9插入左边的序列
将5插入左边的序列
左边的有序序列会慢慢将右边的序列全部包含，最后左边的序列便是我们需要最终有序结果。需要注意的是，在插入数时，需要根据插入数的大小找到相应的插入位置。
下面是可复制代码：
2.时间复杂度
O(n*2)，插入排序的时间复杂度分析较为复杂，有兴趣可以探究一下。
3.空间复杂度
一个额外交换空间，O(1)。
【算法-排序之三】插入排序,布布扣,bubuko.com
【算法-排序之三】插入排序
原文：http://blog.csdn.net/lovecodeless/article/details/21231257
