不需要额外申请空间，从数组的第二个元素即 a[1]开始，将其设为key

用key依次从后【key的前一个元素】比较，当key比当前值小时候，把当前值到Key原位置之间的元素依次向后移动一个单元。

key>=当前值以后，把key复制给当前值后面的值即可。

*保证了Key值之前的所有元素都是sorted的。

void InsertSort(int a[], int n){	int i, j, key;	for (i = 1; i < n; i++)	{		j = i - 1;		key = a[i];		while (j >= 0 && key

空间复杂度O(1);

时间复杂度：

　　　　最好：数组为正序排序，只需要执行for循环，因为key>a[j],直接执行a[j+1]=key即可——O(n)

　　　　最坏：逆序，for+while=O(n^2)

平均就是O(n^2)【对于随机排序的数组，移动和比较次数更接近最坏情况】

稳定：

key