排序算法----插入排序

1、如何进行插入排序

2、程序实现

void InsertSort(int* a,size_t size)
{
	assert(a);
	//注意是size-1
	for(int i = 0;i < size-1;i++)//7 3 6 2 8end只能到2的位置，tmp到8的位置，否则将越界
	{
	    int end = i;
	    int tmp = a[end + 1];
	    while(end >= 0 && tmp < a[end])
	    {
		   a[end+1] = a[end];
		   end--;
	    }
	    a[end+1] = tmp;
	}
}

3、时间复杂度

最好情况是接近所要排序的结果时，为O(N)，例如要升序排序，原数据是接近升序排序的。

最坏情况是与所要排序的方式相反，为O（N*N）例如要升序排序，但原数据是降序排序。