题目描述：

设计函数 void InsertSort(int a[],int n); 该函数使用插入排序算法，将数组a的前n个元素按照升序的方式排序。
插入排序算法描述如下：
初始序列：49 38 65 97 76 13 27 49
将元素(38) 插入合适位置： [38 49] 65 97 76 13 27 49
将元素(65) 插入合适位置： [38 49 65] 97 76 13 27 49
将元素(97) 插入合适位置： [38 49 65 97] 76 13 27 49
将元素(76) 插入合适位置： [38 49 65 76 97] 13 27 49
将元素(13) 插入合适位置： [13 38 49 65 76 97] 27 49
将元素(27) 插入合适位置： [13 27 38 49 65 76 97] 49
将元素(49) 插入合适位置： [13 27 38 49 49 65 76 97]

输入与输出要求：

首先输入一个整数n（1<=n<=1000），代表待排序元素的个数。然后输入n个整数，每个整数不会超过int型的存储范围。
输出为n-1行，依次为1到n-1趟排序后数组内各个元素。每行输出的顺序为a[0]至a[n-1]，数与数之间用空格分开，注意第n个数后没有空格而是换行符。

函数接口定义：

函数原型如下：
void InsertSort(int a[],int n);
其中 a 和 n 都是用户传入的参数。 a 为待排序数组； n 需排序的元素的个数。函数没有返回值。

测试程序样例：

#include<stdio.h>

//插入排序（升序） 
//参数说明：数组，数组中已有元素个数 
void InsertSort(int a[],int n);

int main()
{
    int        n , i,    num[1000] ;

    scanf( "%d" , &n ); 
    for( i = 0 ; i < n ; i++ ) 
        scanf( "%d", &num[i] ) ;
    InsertSort( num , n ) ; 
    return 0 ;
}

输入样例：

8
49 38 65 97 76 13 27 49

输出样例：

38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 97 76 13 27 49
38 49 65 76 97 13 27 49
13 38 49 65 76 97 27 49
13 27 38 49 65 76 97 49
13 27 38 49 49 65 76 97

函数实现-插入排序算法：

void InsertSort(int a[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		if(a[i]>a[i+1])
		{
			int j=i;
			int m=a[i+1];
			while(j>=0&&a[j]>m)//顺序查找
			{
				a[j+1]=a[j];
				j--;
			}
			a[j+1]=m;//插入到目标位置
		}
		
		for(int i=0;i<n-1;i++)
		{
			printf("%d ",a[i]);
		}
		printf("%d\n",a[n-1]);
	}
}

函数实现-冒泡排序算法：

void InsertSort(int a[],int n)
{
	int t;
	for(int k=2;k<=n;k++)
	{
		for(int c=0;c<k-1;c++)//每一趟均使用冒泡排序
		{
		    for(int i=0;i<k-1-c;i++)
	        {
		        if(a[i]>a[i+1])
		        {
			        t=a[i];
			        a[i]=a[i+1];
			        a[i+1]=t;
		        }
		    }
	    }
	    for(int j=0;j<n-1;j++)
		{
			printf("%d ",a[j]);
		}
		printf("%d\n",a[n-1]);
	}
}