题目描述
算法设计：实现直接插入排序。void InsertSort(RecType R[], int n) 为对 R[0…n?1] 按递增有序进行直接插入排序。主函数已经给出。
注意：只提交 void InsertSort(RecType R[], int n) 部分。
#include <stdio.h>
#define MAXE 20 // 线性表中最多元素个数
typedef int KeyType;
typedef char InfoType[10];
typedef struct // 记录类型
{
KeyType key; // 关键字项
InfoType data; // 其他数据项，类型为InfoType
} RecType;
int main()
{
int i, k, n;
KeyType a[100];
RecType R[MAXE];
scanf("%d", &n);
for (i= 0; i < n; i++)
scanf("%d", &a[i]);
for (i= 0; i < n; i++)
R[i].key= a[i];
printf("初始关键字: "); // 输出初始关键字序列
for (k= 0; k < n; k++)
printf("%3d", R[k].key);
printf("\n");
InsertSort(R, n);
printf("最后结果: "); // 输出初始关键字序列
for (k= 0; k < n; k++)
printf("%3d", R[k].key);
printf("\n");
return 0;
}输入
输入待排序元素的个数。
输入待排序的整数。
输出
输出初始数据。
输出排序后的数据。
输入输出样例
样例输入 #1
10
9 2 7 5 6 4 8 3 1 0样例输出 #1
初始关键字: 9 2 7 5 6 4 8 3 1 0
最后结果: 0 1 2 3 4 5 6 7 8 9参考解答：
void InsertSort(RecType R[],int n)
{
int t,i,j;
for(i=1; i<n; i++)
{
if(R[i].key<R[i-1].key)
{
t=R[i].key;
for(j=i-1; j>=0 && R[j].key>t; j--)
{
R[j+1].key=R[j].key;
}
R[j+1].key=t;
}
}
}
?
