6-4 实验7_12_插入排序 (100 分)

设计函数 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)
{
	int i,j,k,temp;
	for(i=1;i<n;i++)
	{
		temp=a[i];
		for(j=0;j<i;j++)
		{
			if(a[i]<=a[j])
			{
				for(k=i;k>j;k--)
			        a[k]=a[k-1];
			    a[k]=temp;
			}
		}
		for(k=0;k<n-1;k++)
		    printf("%d ",a[k]);
		printf("%d\n",a[k]);
	}
}

 

上一篇:【效率为王】Git 使用指南


下一篇:JAVA之旅(十五)——多线程的生产者和消费者,停止线程,守护线程,线程的优先级,setPriority设置优先级,yield临时停止