数据结构⑥：排序算法应用

一、要求：

给出n个学生的考试成绩表，每条记录由学号、姓名和分数和名次组成，设计算法完成下列操作：

设计一个显示对学生信息操作的菜单函数如下所示：

1、录入学生基本信息

2、直接插入排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序

7、2-路归并排序

8、输出学生信息

0、退出

请选择：

算法设计要求：按分数从高到低的顺序进行排序，分数相同的为同一名次。输入的学生信息存入文件中，每选择一种排序方法，必须从文件中取出数据。

二、排序基本思想：

①直接插入排序：

  依次将一个待排序的记录按其关键字的大小插到已排好序的有序表中，从而得到一个新的，记录数增一的有序表。

具体过程：
  初始时R[1]自成一个有序区，无序区为R[2]~R[n].从i=2开始直至i=
n为止，依次将各R[i]插到当前的有序区R[1]~R[i-1]中，生成含有n个记录的有序区。
  当插入第i（i>=1）个记录时，前面的R[1]~R[i-1]已经排好序。此时，用R[i]的关键字与R[i-1]，R[i-2],…,R[1]的关键字顺序进行比较，找到插入位置，将R[i]插入，原来位置及其以后的所有记录依次后移。

②冒泡排序：

  对于长度为n的待排序序列，从前向后，对相邻的两个元素两两进行比较，若是逆序，则交换两个元素的值，以此类推，直至对第n-1个记录和第n个记录进行比较为止。

③快速排序：

  通过一趟排序将待排序列记录分割成独立的两部分，其中一部分的关键字均不大于另一部分的关键字，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

具体过程：
  对R[s],…,R[t]中的记录进行一趟快速排序，附设两个指针low,high，设置一个枢轴记录R[0]=R[s]，pivockey=R[s].key。
令low=s，high=t，并保存low的记录；
  从high所指位置起向low所指位置方向搜索，找到第一个关键字不大于pivockey的记录，放在low位置处，并使low++；从low所指位置起向high所指位置方向搜索，找到第一个关键字不小于pivockey的记录，放在high位置处，并使high–。重复该步骤，知道low=high为止。
  将轴元素放在low处。再分别对两个子序列进行快速排序，直至每一个子序列只含有一个记录为止。

④简单选择排序：

  第i（1<=i<n）趟排序通过n-i次关键字的比较，在n-i+1个记录中选择具有最小关键字的记录，并和第i个记录进行交换。重复此操作n-1次，最终得到一个有序序列。

⑤堆排序：

  以大顶堆为例，将无需序列建成一个堆，得到关键字最大的记录，将堆顶元素与最后一个元素进行交换，将堆顶元素输出。从根结点开始，自上而下进行调整。将堆顶元素与左右子树的根结点中关键字较大者进行比较，若堆顶元素小于子树根结点的值，则堆顶结点与子树根结点交换。重复上述过程，直到该子树满足堆的性质为止。
重复上述过程，直至得到一个有序系列。

⑥2-路归并排序：

  把n个记录看成n个长度为1的有序子表；
  对相邻两个子表进行归并使记录按关键字有序排列，得到n/2个长度为2的有序子表。重复该步骤直到所有记录归并成一个长度为n的有序表为止。

三、代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 20  //学生最多人数
typedef struct{
	char num[20];  //学号
	char name[20];  //姓名
	int score;   //分数
}stu;
typedef struct{
	 stu R[MAXSIZE+1]; //0单元作为监视哨
	 int length;
}Sqlist;


void menu(){
	printf("**************************\n");
	printf("\t1. 录入学生基本信息\n");
	printf("\t2. 直接插入排序\n");
	printf("\t3. 冒泡排序\n");
	printf("\t4. 快速排序\n");
	printf("\t5. 简单选择排序\n");
	printf("\t6. 堆排序\n");
	printf("\t7. 2-路归并排序\n");
	printf("\t8. 输出学生信息\n");
	printf("\t0. 退出\n");
	printf("**************************\n");
	printf("请选择:\n");
}

void InputInformation(Sqlist &L){
	int i;
	FILE *fp;
	if((fp=fopen("stdinf.txt","w"))==NULL){
		printf("无法打开该文件!\n");
		return ;
	}
	printf("请输入学生人数:");  
    scanf("%d",&L.length);
	printf("请输入学生的学号,姓名,分数\n");
	for(i=1;i<=L.length;i++){
		scanf("%s%s%d",L.R[i].num,L.R[i].name,&L.R[i].score);
		fprintf(fp,"%8s%8s%8d\n",L.R[i].num,L.R[i].name,L.R[i].score);
	}//while
	fclose(fp);
}
void Readfile(Sqlist L){
	FILE *fp;
	int i;
	fp = fopen("stdinf.txt","r");
	for(i=1;i<=L.length;i++)  
        fscanf(fp,"%s %s %d\n",L.R[i].num,L.R[i].name,&L.R[i].score);  
	fclose(fp);
}
/********直接插入排序*********/
void InsertSort(Sqlist &L){
	int i,j;
	for(i=2;i<=L.length;i++)
		if(L.R[i].score > L.R[i-1].score){
			L.R[0] = L.R[i];  //R[i]为哨兵
			L.R[i] = L.R[i-1];
			for(j=i-2;L.R[0].score >L.R[j].score;j--)
				L.R[j+1] = L.R[j];
			L.R[j+1] = L.R[0];
		}//if
}
/***冒泡排序 ****/
void BubbleSort(Sqlist &L){
	int flag=1,i,j;
	for(i=1;i<=L.length && flag;i++){
		flag = 0;
		for(j=1;j<=L.length-i;j++)
			if(L.R[j].score < L.R[j+1].score){
				L.R[0] = L.R[j];	L.R[j] = L.R[j+1];
				L.R[j+1] = L.R[0];	flag = 1;
			}//if
	}//for
}
/****快速排序*****/
int Partition(Sqlist &L,int low,int high){
	int pivotscore = L.R[low].score;
	L.R[0] = L.R[low];
	while(low<high){
		while(low<high && L.R[high].score <= pivotscore)
			high--;
		if(low<high)
			L.R[low++] = L.R[high];
		while(low<high && L.R[low].score >= pivotscore)
			low++;
		if(low<high)
			L.R[high--] = L.R[low];
	}//while
	L.R[low] = L.R[0];
	return low;
}
void QSort(Sqlist &L,int low,int high){
	int pivotloc;
	if(low<high){
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1);
		QSort(L,pivotloc+1,high);
	}
}
void QuickSort(Sqlist &L){
	QSort(L,1,L.length);
}
/****简单选择排序****/
void SelectSort(Sqlist &L){
	int i,j,k;
	for(i=1;i<L.length;i++){
		k = i;
		for(j=i+1;j<=L.length;j++)
			if(L.R[k].score < L.R[j].score )
				k = j;
		if(i!=k){
			L.R[0] = L.R[k]; L.R[k] = L.R[i]; L.R[i] = L.R[0];
		}//if
	}//for
}
/******堆排序*******/
void HeapAdjust(Sqlist &L,int s,int m){
	int j;
	L.R[0] = L.R[s];
	for(j=2*s;j<=m;j*=2){
		if(j<m && L.R[j].score > L.R[j+1].score)    //沿k较小的结点向下筛选
			j++;                           //j为score较小记录的下标
		if(L.R[0].score <= L.R[j].score )
			break;
		L.R[s] = L.R[j]; s=j;
	}//for
	L.R[s] = L.R[0];  //插入
}
void HeapSort(Sqlist &L){
	int i,t;
	for(i=L.length/2;i>0;i--)   //建立初始堆
		HeapAdjust(L,i,L.length);
	for(i=L.length;i>1;i--){
		t = L.R[1].score; L.R[1].score = L.R[i].score; L.R[i].score = t;
		HeapAdjust(L,1,i-1);
	}
}
/******2-路归并排序******/
void Merge(Sqlist &L,int s,int m,int n){
	int i,j,k;
	Sqlist T;
	i=s; j=m+1; k=0;
	while(i<=m && j<=n)   //归并两个相邻的有序表
		if(L.R[i].score>=L.R[j].score)
			T.R[k++] = L.R[i++];
		else
			T.R[k++] = L.R[j++];
	while(i<=m)
		T.R[k++] = L.R[i++];
	while(j<=n)
		T.R[k++] = L.R[j++];
	for(i=s;i<=n;i++)    //将T表中的元素复制到表L中
		L.R[i] = T.R[i-s];
}
void MSort(Sqlist &L,int low,int high){
	int mid;
	if(low<high){
		mid=(low+high)/2;
		MSort(L,low,mid);
		MSort(L,mid+1,high);
		Merge(L,low,mid,high);
	}
}
void MergeSort(Sqlist &L){
	MSort(L,1,L.length);
}
/*****输出学生信息*****/
void show(Sqlist L){
	int i;
	int rank=1,index=0;
	FILE *fp;
	if((fp=fopen("stdinf.dat","w"))==NULL){
		printf("无法打开该文件!\n");
		return ;
	}
	printf("输出排名后所有学生的信息\n");
	printf(" 名次	姓名	学号	分数\n");
	for(i=1;i<=L.length;i++){
		printf("%6d%8s%7s%7d\n",rank,L.R[i].name,L.R[i].num,L.R[i].score);
		if(i<L.length && L.R[i].score==L.R[i+1].score)
			index++;
		else{
			rank+=index+1;
			index=0;
		}//else
	}
	fclose(fp);
}
/*******主函数********/
int main(){
	Sqlist L;
	int choice;
	while(1){
		menu();
		scanf("%d",&choice);
		switch(choice){
			case 1: InputInformation(L);break;
			case 2:	Readfile(L); InsertSort(L);break;
			case 3:	Readfile(L); BubbleSort(L);break;
			case 4: Readfile(L); QuickSort(L);break;
			case 5: Readfile(L); SelectSort(L);break;
			case 6: Readfile(L); HeapSort(L);break;
			case 7: Readfile(L); MergeSort(L);break;
			case 8: Readfile(L); show(L);break;
			case 0: return 0;
			default:printf("\n\t输入错误，请重新选择!\n");
		}//switch
	}//while
}

结果：

Directions:

 仅代表初始数据结构时思路。