实验目的掌握常用的排序方法，并掌握用高级语言实现排序的算法。
深刻理解排序的定义和各种排序方法的特点，宾能加以灵活应用。
了解各种方法的排序过程以及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二 实验内容
1统计成绩
[为题描述]给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
按分数高低顺序，打印出每个学生在考试中获得的名词，分数相等的为同一名次；
安名次列出每一个学生的姓名和成绩。
[基本要求]学生的成绩必须通过键盘输入数据建立，同时要对输出进行格式控制。
[算法实现]下面给出的使用直接选择排序算法实现的C语言程序。在此基础上读者可以尝试用直接插入，shell排序，冒泡排序，快续排序归并排序等算法实现本问题的求解
#define n 30
typedef strucr student
{char name[8];
int score;
}
student r[n];
main()
{int num,I,j,max,temp;
printf(“请输入学生成绩”);
for(I=0;I<n;I++)
{printf(“姓名：“)；
scanf(stu[I].name);
scanf(&stu[I].score);
}
num=1;
for(I=0;I<n;I++)
{max=I;
for(j=I+1j<n;j++)
if(r[j].score>r[max].score)
max=j;
if(max!=I)
{temp=r[max];
r[max]=r[I];
r[I]=temp;
}
if((I>0)&&(r[I].score<r[I-1].score))
num=num+1;
printf(num,r[I].name,r[I].score);
}
}
2.采用最小意义关键字优先的基数排序法，实现对数的排序，数列中的每个数据由d位数字组成，不足 d位的高位补0。
[算法提示]设待排序数序列为r1,r2,r3…..r n,他们各自的关键字为k1,k2….kn;其中每个关键字由d个分量组成，ki^d,ki^d-1…ki^1,其中ki^1位最大意义关键字分量，ki^d为最小意义关键字分量，从而将数据按关键字分量ki^d,ki^d-1…ki^1的顺序对数据排序。
设待排序的数据均由3位数组成，即d=3;显然，每个数据由分量ki^3,ki^2,ki^1组成，ki^1表示第一位，ki^2 表示第二位,ki^3表示第三位。
由于待排序数据为序列，则每位上的数据由0-9种的某个数组成，故可设置10个队列，用数组f和e的元素fi,ei 分别表示队列的开头和结尾（I=0-9）,只要每一次排序前先将各队列置空，然后按ki^3,ki^2,ki^1的顺序对其排序即可.
为了使排序过程尽可能地不进行数列中的数据移动，可设计结点为一包含关键字域key和指针域next的结构体。于是，第I各队列由fi和ei分别存放该队列中的一个数据和最后一个数据在序列中的位置下标值。数列在进行排序前，之后及排序过程中，各对列中各个数据的先后顺序通过指针域next的链域来实现，可由变量p来指示排序后这个有序数列的第一个元素的位置。
[算法实现]
#define d 3//关键字位数为3
#define m 10//基数10
typedef struct
{int key[d];//关键字由d个分量组成
int next;//静态指针域next
datatype other;//其他域
}rectype;
typedef struct
{int f,e;//n个队列的首指针，和尾指针
}queue;
queue b[m];//用对列表示
//对r[0]到r[n-1]进行基数排序，返回收集用的链头指针
int basesort?
rectype r[];
{int I,j,k,t,p;
for(I=0;I<n;I++)//将 r[0]到r[n-1]链成一个静态表
r[I],next=I+1;
r[n-1].next=-1;//将初始链表的终端结点指针置空
p=0;
for(j=d-1;j>=0;j--)//进行d趟排序
for(I=0;I<m;I++)//清空对列
{
b[I].f=-1;
b[I].e=-1;
}
while(p!=-1)//按关键字第j个分量进行分配
{k=r[p].key[j];
if(b[k].f==-1)
b[k].p;//对列为空时，将 r[p]链到队列头部
else
r[b[k].e].next=p;//否则对列非空将r[p]链到队尾
b[k].e=p;//修改对列的尾指针
p=r[p].next;//扫描下一个记录
}
I=0;
While(b[I].f==-1)//检索第一个非空队列
I++;
t=b[I].e;
p=b[I].f//p尾收集链表的头指针
while(I<m-1)//检索下一个对列
{I++;
if(b[I].f!=-1)//队列非空时链接
{
r[t].next=b[I].f;
t=b[I].e;
r[t].next=-1;//本唐收集完毕，将链表的终端结点指针置空
}
return p;
}
3写出含有n个元素的队中增加一个元素，且调整为堆的算法
［算法提示］由于堆可看成一棵完全二叉树，所以可以用一个数组r[1]至r[n+1]表示一个堆。其中r[1]到r[n]表示原始堆中的各个元素，r[n+1]用于存放新插入的元素。由于原来的n个元素已经构成堆，则当插入一个元素时，有可能破坏堆的结构，所以需依据情况进行调整，此时仅需要从r[n+1]出发,
走一条从叶子结点r[n+1]到根结点r[1]的路径（设为小根堆）。每次就该结点r[j]和其双亲结点r[I]进行比较，若r[I].key>r[I].key，此时算法结束，不需要进行调整，此时r[1]到r[n+1]即为堆，否则，将r[I]与r[j]进行交换，继续和上一层结点比较，直到根结点为止。
[算法实现]
#define n 15
#define datatype int
typedef struct
{int key;//关键字域
datatype other;//其它域
}rectlype;
rectype r[n];
//在堆r[1]到r[n]中插入一个新元素
heapinsert(r,x)
rectype r[];
datatype x;
{
int I,j;
j=n+1;
while(j>1)
{I=j/2;//求结点kj的双亲结点ki
if(r[I].key<x.key)j=1;//若此时为堆跳出循环
else
{r[j]=r[I];
j=I;
}//不为堆在调整
}
r[I]=x;//x插入正确的插入位置
}
main()
{int n,I;
datatype x;
for(I=1;I<=n;I++)
{scanf(r[I]);
printf(r[I]);
}
scanf(&x);
heapinsert(r,x);
for(I=1;I<=n+1;I++)
printf(r[I]);
}
4.输入若干国家名称，请按字典顺序将这些国家进行排序（设所有的名称钧用大写或小写表示）。
［算法提示］本提实质是对一些字符串进行排序，可以用直接选择排序或shell排序等，这里shell采用排序。Shell排序又称“缩小增量排序”它的做法是：先取一个小于n的整数d１作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，再每一个组织结进行插入排序；然后，取第二个增量d2<d1重复上述分组和排序，直至所取得增量dt=1(dt<dt-1…<d1),
及所有记录放入同一组中进行直接插入排序为止。
［算法实现］
// 按字典顺序将这些国家进行排序
main()
{
string r[];
string temp;
int I,h,n,change;
scanf(&n);
printf(“input country name\n”);
for(I=0;I<n;I++)
scanf(r[I]);
h=n;
while(h>0)
{
h=h/2;//取增量h/2
do
{
change=false;
for(I=0;I<n-h;I++)
if(r[I]>r[I+h])//比较
｛temp=r[I];//交换
r[I]=r[I+h];
r[I+h]=temp;
change=true;//置已交换标志
}
}while(!change);
}
printf(“output country name\n”);
for(I=0;I<n;I++)
printf(r[I]);
}
深刻理解排序的定义和各种排序方法的特点，宾能加以灵活应用。
了解各种方法的排序过程以及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。
二 实验内容
1统计成绩
[为题描述]给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：
按分数高低顺序，打印出每个学生在考试中获得的名词，分数相等的为同一名次；
安名次列出每一个学生的姓名和成绩。
[基本要求]学生的成绩必须通过键盘输入数据建立，同时要对输出进行格式控制。
[算法实现]下面给出的使用直接选择排序算法实现的C语言程序。在此基础上读者可以尝试用直接插入，shell排序，冒泡排序，快续排序归并排序等算法实现本问题的求解
#define n 30
typedef strucr student
{char name[8];
int score;
}
student r[n];
main()
{int num,I,j,max,temp;
printf(“请输入学生成绩”);
for(I=0;I<n;I++)
{printf(“姓名：“)；
scanf(stu[I].name);
scanf(&stu[I].score);
}
num=1;
for(I=0;I<n;I++)
{max=I;
for(j=I+1j<n;j++)
if(r[j].score>r[max].score)
max=j;
if(max!=I)
{temp=r[max];
r[max]=r[I];
r[I]=temp;
}
if((I>0)&&(r[I].score<r[I-1].score))
num=num+1;
printf(num,r[I].name,r[I].score);
}
}
2.采用最小意义关键字优先的基数排序法，实现对数的排序，数列中的每个数据由d位数字组成，不足 d位的高位补0。
[算法提示]设待排序数序列为r1,r2,r3…..r n,他们各自的关键字为k1,k2….kn;其中每个关键字由d个分量组成，ki^d,ki^d-1…ki^1,其中ki^1位最大意义关键字分量，ki^d为最小意义关键字分量，从而将数据按关键字分量ki^d,ki^d-1…ki^1的顺序对数据排序。
设待排序的数据均由3位数组成，即d=3;显然，每个数据由分量ki^3,ki^2,ki^1组成，ki^1表示第一位，ki^2 表示第二位,ki^3表示第三位。
由于待排序数据为序列，则每位上的数据由0-9种的某个数组成，故可设置10个队列，用数组f和e的元素fi,ei 分别表示队列的开头和结尾（I=0-9）,只要每一次排序前先将各队列置空，然后按ki^3,ki^2,ki^1的顺序对其排序即可.
为了使排序过程尽可能地不进行数列中的数据移动，可设计结点为一包含关键字域key和指针域next的结构体。于是，第I各队列由fi和ei分别存放该队列中的一个数据和最后一个数据在序列中的位置下标值。数列在进行排序前，之后及排序过程中，各对列中各个数据的先后顺序通过指针域next的链域来实现，可由变量p来指示排序后这个有序数列的第一个元素的位置。
[算法实现]
#define d 3//关键字位数为3
#define m 10//基数10
typedef struct
{int key[d];//关键字由d个分量组成
int next;//静态指针域next
datatype other;//其他域
}rectype;
typedef struct
{int f,e;//n个队列的首指针，和尾指针
}queue;
queue b[m];//用对列表示
//对r[0]到r[n-1]进行基数排序，返回收集用的链头指针
int basesort?
rectype r[];
{int I,j,k,t,p;
for(I=0;I<n;I++)//将 r[0]到r[n-1]链成一个静态表
r[I],next=I+1;
r[n-1].next=-1;//将初始链表的终端结点指针置空
p=0;
for(j=d-1;j>=0;j--)//进行d趟排序
for(I=0;I<m;I++)//清空对列
{
b[I].f=-1;
b[I].e=-1;
}
while(p!=-1)//按关键字第j个分量进行分配
{k=r[p].key[j];
if(b[k].f==-1)
b[k].p;//对列为空时，将 r[p]链到队列头部
else
r[b[k].e].next=p;//否则对列非空将r[p]链到队尾
b[k].e=p;//修改对列的尾指针
p=r[p].next;//扫描下一个记录
}
I=0;
While(b[I].f==-1)//检索第一个非空队列
I++;
t=b[I].e;
p=b[I].f//p尾收集链表的头指针
while(I<m-1)//检索下一个对列
{I++;
if(b[I].f!=-1)//队列非空时链接
{
r[t].next=b[I].f;
t=b[I].e;
r[t].next=-1;//本唐收集完毕，将链表的终端结点指针置空
}
return p;
}
3写出含有n个元素的队中增加一个元素，且调整为堆的算法
［算法提示］由于堆可看成一棵完全二叉树，所以可以用一个数组r[1]至r[n+1]表示一个堆。其中r[1]到r[n]表示原始堆中的各个元素，r[n+1]用于存放新插入的元素。由于原来的n个元素已经构成堆，则当插入一个元素时，有可能破坏堆的结构，所以需依据情况进行调整，此时仅需要从r[n+1]出发,
走一条从叶子结点r[n+1]到根结点r[1]的路径（设为小根堆）。每次就该结点r[j]和其双亲结点r[I]进行比较，若r[I].key>r[I].key，此时算法结束，不需要进行调整，此时r[1]到r[n+1]即为堆，否则，将r[I]与r[j]进行交换，继续和上一层结点比较，直到根结点为止。
[算法实现]
#define n 15
#define datatype int
typedef struct
{int key;//关键字域
datatype other;//其它域
}rectlype;
rectype r[n];
//在堆r[1]到r[n]中插入一个新元素
heapinsert(r,x)
rectype r[];
datatype x;
{
int I,j;
j=n+1;
while(j>1)
{I=j/2;//求结点kj的双亲结点ki
if(r[I].key<x.key)j=1;//若此时为堆跳出循环
else
{r[j]=r[I];
j=I;
}//不为堆在调整
}
r[I]=x;//x插入正确的插入位置
}
main()
{int n,I;
datatype x;
for(I=1;I<=n;I++)
{scanf(r[I]);
printf(r[I]);
}
scanf(&x);
heapinsert(r,x);
for(I=1;I<=n+1;I++)
printf(r[I]);
}
4.输入若干国家名称，请按字典顺序将这些国家进行排序（设所有的名称钧用大写或小写表示）。
［算法提示］本提实质是对一些字符串进行排序，可以用直接选择排序或shell排序等，这里shell采用排序。Shell排序又称“缩小增量排序”它的做法是：先取一个小于n的整数d１作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，再每一个组织结进行插入排序；然后，取第二个增量d2<d1重复上述分组和排序，直至所取得增量dt=1(dt<dt-1…<d1),
及所有记录放入同一组中进行直接插入排序为止。
［算法实现］
// 按字典顺序将这些国家进行排序
main()
{
string r[];
string temp;
int I,h,n,change;
scanf(&n);
printf(“input country name\n”);
for(I=0;I<n;I++)
scanf(r[I]);
h=n;
while(h>0)
{
h=h/2;//取增量h/2
do
{
change=false;
for(I=0;I<n-h;I++)
if(r[I]>r[I+h])//比较
｛temp=r[I];//交换
r[I]=r[I+h];
r[I+h]=temp;
change=true;//置已交换标志
}
}while(!change);
}
printf(“output country name\n”);
for(I=0;I<n;I++)
printf(r[I]);
}
