排序之插入排序：从斗地主到插入排序

1.斗地主如何摸牌

2.从摸牌想到插入排序

3.完成插入排序

4.结束语

1.斗地主如何摸牌

不知道各位是否玩过几乎人人都玩过的斗地主游戏呢？相必各位或多或少都玩过一点，再没玩过也看别人打过。今天博主就将从这个游戏为大家讲解我们的插入排序。

在每一个斗地主玩家开始打牌前，我们都要经历一个摸牌的过程，不知道各位有木有发现，我们是怎么做到手上的牌如此整齐的呢？

其实各位只要稍微回想一下，就会发现我们是拿一张就往牌里插入，找到那个比前面小比后面打的牌。而这个过程其实就是我们的插入排序的过程。

2.从摸牌想到插入排序

在这里博主做了一个小小的动态图来模仿各位的动态图。橙色的是我们手上的动态，而蓝色的则是相当于我们还没摸的牌。当然博主这个已经不再只是前面的摸牌了而是进入我们的数字排序了。

正所谓高山来自积石，长河来自水滴。我们任何一个大的程序的完成都要从小的步骤开始做，那么我们该如何用代码去完成这中间的每一个小过程呢？

其实只要稍微模拟一下我们摸牌时候的思路就可以了，即插入的牌的位置，要比我们的后面的牌小，在我们每次向后找位置时，比我们大的牌也在向后走的，就如上面的动态图一样。

int end;//数组的最后一个->即手上的牌最大的那个
int tmp;//要插入的数字
while (end >= 0)
{
	if (a[end] > tmp)//如果这个数比你插入的大
	{
		a[end + 1] = a[end];//这个数字向后移
		end--;//再往前面次大的数字比
	}
	else//你比这个数字大或者等于
	{
		break;
	}
	a[end + 1] = tmp;//你在你比小的数的位置的前面

那么用代码去完成就是这样的。不知道是否是你心中的答案呢？

3.完成插入排序

那么上面我们已经完成了单步的插入，那我们后面的插入又该如何完成呢？其实也蛮简单的，因为在实际上我们的第一张牌时不用排序的，那么我们依次将后面的第二张牌，第三张牌插入就可以了，最后我们封装成一个小程序就是这样：

void InsertSort(int *a,int n)
{
	for (int i = 1; i < n; i++)
	{
		//[0,end]有序数组
		int end=i-1;//第一次最后一个数就是a[0]的位置
		int tmp=i;//永远在已排好数组的后面一个
		while (end >= 0)//插入
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
			a[end + 1] = tmp;
		}
	}
	
}