/* 插入排序 */void InsertionSort(int a[]) {	int i, j;	for (j = 1; j < 9; j++) {		int item = a[j]; /* 待插入有序数组部分的数 */		for (i = j - 1; i >= 0; i--) {			if (a[i] > item)				a[i + 1] = a[i]; /* 从后往前将有序数组中大于item的元素a[i]后移一位 */			else				break;		}		a[i + 1] = item; /* 将item插入 */	}}
在最好情况下，输入的数组是已经排好了序的 时间复杂度为O(n).
在最坏情况下，输入的数组是逆序的 时间复杂度为O(n^2).
平均情况下：在已排序的数组a[0~j-1] 中的元素 前一半的元素比a[j]小  后一半的元素比a[j]大. 时间复杂度亦为O(n^2).

插入排序是稳定的。