算法思想：

　　对于一个已排好序的数组，只要将新加入的元素插入到相应的位置，该数组仍是排序数组。

算法实现：

INSERTION_SORT(A)
     for i in 1 to lenthOf A -1
         value = A[i]
         for j in i-1 to 0
             if A[j] >= value
                 break
             swap A[j] A[j+1]      
         A[j+1] = value

算法复杂度：

　　平均：O(n^2)

　　最差：O(n^2)

　　最好：O(n)

使用场景：

　　插入排序由于有较差的时间复杂度，一般不用于大量数据排序的场景，但由于算法实现的紧密性，对与少量数据来说是一个快速的原地排序算法，另外，对于大部分都排好序的序列来说，插入排序是比较快速的，因此一般作为其他排序算法的补充(如快速排序等)

STL中的实现：

　　STL中没有插入排序的直接实现，但其作为其他排序的补充优化，在sort、stable_sort等中均有用到

插入排序,布布扣,bubuko.com

插入排序

原文：http://www.cnblogs.com/stormli/p/insertion_sort.html