C/C++学习教程：C语言排序算法—插入排序算法
前言：插入排序算法是所有排序方法中最简单的一种算法，其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据。
直接插入排序是插入排序算法中的一种，采用的方法是：在添加新的记录时，使用顺序查找的方式找到其要插入的位置，然后将新记录插入。
很多初学者所说的插入排序，实际上指的就是直接插入排序算法，插入排序算法还包括折半插入排序、2-路插入排序，表插入排序和希尔排序等。
直接插入排序的基本操作是将一个记录插入到已经排好的有序表中。
先选定一个位置i，插入排序将i左侧比位置i数值大的数值全部右移，然后将原来i对应的值插入回去。
voidInsertSort(int*p){int i,j;inttmp=0;for(i=1;i<10;i++)
{if(p[i-1]>p[i]) {tmp = p[i];//将p[i]左边比p[i]大的全部左移，要先将其赋给一个缓存变量
for(j=i-1;p[j]>tmp;j--)
{p[j+1]=p[j];
}p[j+1]=tmp;
} }}
过程，先将p[i]的值赋给tmp，然后i左侧的数值与tmp比较，比tmp大则右移一位，不比tmp大，则将tmp插入回去。
最好情况下，即要排序的序列本身是有序的，第7行的比较一共执行了n-1次，没有移动记录，时间复杂度为O(n)。
最坏情况下，需要比较2+3+...+n=(n+2)(n-1)/2次，移动次数为(n+4)(n-1)/2
时间复杂度为O(n2)