数据结构插入排序

插入排序

什么是插入排序呢？

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
这是我在老师课堂里的笔记中摘抄下来的，我自己理解，插入排序其实就是，假设前n-1个有序，将第n的数插到已经有序的数组中。

代码实现
直接写，可能会有点困难，我们可以先写单个循环，拿第n个数或者说有序数组中最后一个数（end）的后一个数和end+1做比较，如果第end个数>第end+1个数，则交换，然后再继续与前面那个数作比较，否则就是放在那个位置上。（看文字描述可能有点懵，看代码就会好的多）

//升序
int end ;
int tmp = a[end+1];
while(end >=0)
{
	if(a[end]>tmp)//一直是拿下标是end+1的数进行比较
	{
		a[end+1] = a[end];
		end--;
	}
	else
	{
		break;
	}
}
a[end+1] = tmp;

再补全，假设第一个数就是有序的，走完上一趟，下标为0，1的就有序啦，所以end一直加加就行了，这时可以用for循环来控制，直到最后一个下标为n-2.

void InsertSort(int* a ,int n)
{
	for(int i = 0; i < n-1; i++)
	{
		int end = i;
		int tmp = a[end+1];
		while(end >=0)
		{
			if(a[end]>tmp)//一直是拿下标是end+1的数进行比较
			{
				a[end+1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end+1] = tmp;
	}
}