算法思想：

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

算法实现：

INSERTION_SORT(A)     for i in 1 to lenthOf A -1         value = http://www.mamicode.com/A[i]>

算法复杂度：

　　平均：O(n^2)

　　最差：O(n^2)

　　最好：O(n)

使用场景：

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

STL中的实现：

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