C语言深入浅出讲解直接插入排序算法的实现

//[0, end]已经有序，将end+1位置的值插入到[0,end]中，使得[0,end+1]依旧保持有序
//有一个有序区间，插入一个数据，依旧保持有序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	//控制摸牌的过程，一开始从仅一张开始
	//注意循环结束条件，只需要到n-2的位置，若将其改成i<n，则会出现越界的情况
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)//保证牌是有序的
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//往后挪，注意画图感受哦
				end--;
			}
			else
			//有两种可能：（现想常规的，再考虑特殊情况）
			//一是找到了比它小的数，放到其后；
			//二是没有比它小的数，直到end为-1才结束
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}