直接插入排序

将待排序列看做左右两个子序列，左子序列有序。则一趟直接插入的排序过程为：对于右侧序列的第一个记录，在左侧有序序列中找到一个合适的位置，插入。从后向前查找合适的位置，同时向后移动记录。

代码如下：

/* 直接插入排序 */
void StraightInsertionSort(int a[], int n)
{
	int i, j, k, tmp;
	for (i=1; i<n; i++)	// 假定a[0]有序
	{
		tmp = a[i];	// 待排记录
		// 从后向前查找插入位置，同时将已排序记录向后移动
		j = i - 1;
		while (j > -1 && tmp < a[j])
		{
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = tmp;	// 将待排记录放到合适位置
	}
}

直接插入排序的时间复杂度为O(n2)，空间复杂度为O(1)。