所谓插入排序法，就是检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。

    假设我们输入的是 “5，1，4，2，3” 我们从第二个数字开始，这个数字是1，我们的任务只要看看1有没有正确的位置，我们的做法是和这个数字左边的数字来比，因此我们比较1和5，1比5小，所以我们就交换1和5，原来的排列就变成了“1，5，4，2，3 ”

    接下来，我们看第3个数字有没有在正确的位置。这个数字是4，它的左边数字是5，4比5小，所以我们将4和5交换，排列变成了 “1，4，5，2，3 "我们必须继续看4有没有在正确的位置，4的左边是1，1比4小，4就维持不动了。

/********************************************************************** 
 *功能描述：插入法排序 
 *输入参数： 数组， 起始索引(0), 终止索引
 *输出参数： 排好序的数组
 *返回值： void
 *其它说明： 
 *修改记录1：   //修改历史记录，包括修改日期、版本号、修改人及修改内容等 
 *修改日期        版本号              修改人         修改内容 
 * -------------------------------------------------------------------------------------------------- 
 * 20140716         V1.0              wuyq            创建 
 ***********************************************************************/ 
void insertion_sort(int array[], int first, int last)
{
	int i,j;
	int temp;
	for(i=first+1; i<=last; i++)
	{
		temp=array[i];
		j=i-1;
		//与已排序的数逐一比较，大于temp时，该数移后
		while((j>=first)&&(array[j]>temp))
		{
			array[j+1]=array[j];
			j--;
		}
		array[j+1]=temp;
	}
}
/********************************************************************** 
 *功能描述：插入法排序 
 *输入参数： 数组， 元素个数
 *输出参数： 排好序的数组
 *返回值： void
 *其它说明： 
 *修改记录1：   //修改历史记录，包括修改日期、版本号、修改人及修改内容等 
 *修改日期        版本号              修改人         修改内容 
 * -------------------------------------------------------------------------------------------------- 
 * 20140716         V1.0              wuyq            创建 
 ***********************************************************************/ 
void insert_sort(int* array, unsigned int n)
{
	int i,j;
	int temp;
	for(i=1;i<n;i++)
	{
		temp=*(array+i);
		for(j=i;j>0&&*(array+j-1)>temp;j--)
		{
			*(array+j)=*(array+j-1);
		}
		*(array+j)=temp;
	}
}

#include <stdio.h>

int main()
{
	int a[8] = {5, 6, 2, 7, 2, 0, 1, 4};
	//insertion_sort(a, 0, 7);
	insert_sort(a, 8);
	int i;
	for(i=0; i<8; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	
	return 0;
}