插入排序

算法思想：

　　若序列S_i为已排序序列，对于到来的第i+1个元素A_i+1，只要将将它插入到S_i的合适位置，新序列S_i+1即为已排序序列

算法实现：

 1 void insertion_sort( int A[], int n )
 2 {
 3     for( int i = 1; i < n ; i ++ )
 4     {
 5         int j = i-1 ;
 6         int temp = A[i];
 7         while( j >= 0 && A[j] > temp )
 8         {
 9             A[j+1] = A[j--];
10         }
11         A[j+1] = temp;
12     }
13 }

View Code

算法复杂度：

　　平均：O(n²)

　　最差：O(n²)

　　最好：O(n)

使用场景：

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

STL中的实现：

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