数据结构与算法复习（二）插入排序
算法描述：
插入排序将数组分成有序和无序两个部分，每次排序选择无序部分的第一个元素与有序部分从后到前比较，找到适当位置插入。插入排序是一种稳定排序。
比如数组
7 6 8 9 2 10
刚开始排序时，有序部分只有一个元素7，无序部分为6 8 9 2 10；取无序部分第一个元素6与有序部分从后到前比较，插入到适当位置，则有序部分变为6 7，无序部分为8 9 2 10
6 7 8 9 2 10
继续选择无序部分第一个元素8，与有序部分从后到前比较，插入适当位置，有序部分变为6 7 8，无序部分为9 2 10
6 7 8 9 2 10
一直重复上述过程，直到将最后一个无序元素10插入完成
算法C语言实现如下
1 void insertSort(int A[], int len) 2 { 3 int P, j; 4 int tmp; 5 6 if (A == NULL || len <= 1) { 7 return; 8 } 9 10 for (P = 1; P < len; p++) { 11 tmp = A[P]; 12 for (j = P; j > 0 && A[j - 1] > tmp; j--) { 13 A[j] = A[j - 1]; 14 } 15 A[j] = tmp; 16 } 17 }
空间复杂度：
只需要一个临时缓存tmp，空间复杂度为O(1)
时间复杂度：
最好情况：已经有序，那么只要比较（N-1）次；
最坏情况：刚好逆序，对于每一个P值，都要执行P+1次A[j]赋值操作，运行时间为O(N2)
插入排序的平均情形是O(N2)，因此，插入排序适合数据量小的情况。