[键入公司名称]数据结构实验报告——排序实验四实验目的和要求：掌握各种排序方法的排序过程；了解一些排序算法的实现，如插入排序、选择排序、冒泡排序、快速排序、堆排序等。实验原理：1.排序的相关术语：内部排序：对内存中的数据进行排序，即排序不涉及数据内、外存交换。外部排序：按照某种策略将外存数据分批调入内存进行排序，从而达到整体有序。排序时涉及数据的内、外存交换。关键字：用于标识记录的数据项。排序方法的稳定性：具有相同关键字的记录之间相对次序保持不变的排序方法是稳定的，否则是不稳定的。堆：关键字K1，K2，…Kn构成堆当且仅当排序满足如下性质：Ki<=K2i且Ki<=K2i+1或Ki>=K2i且Ki>=K2i+1(1<=i<=n/2)就地排序：排序算法所需的辅助空间不依赖于问题的规模n.2.排序方法：插入排序：a.直接插入排序b.希尔排序：将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。交换排序：a.冒泡排序b.快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小。然后分别对这两部分记录继续进行排序，以达到整个序列有序。选择排序：a.简单选择排序b.堆排序归并排序：将两个或两个以上的有序表组合成一个新的有序表。实验内容：学生成绩由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生信息实现：按分数的高低排序，打印每个学生在考试中的排名，分数相同的为同一名次，同一名次的同学按学号从小到大排列。按照名次列出每个学生的名次、学号、姓名和成绩。程序设计：程序设计思想：建立一个学生类：其中包含学生的基本信息：学号、姓名成绩以及名次。主函数包括：学生信息输入函数：要求从键盘上输入学生的学号、姓名、以及成绩。学生成绩排序函数：按照学生成绩排序——冒泡排序，用一个数组b[n]记录学生的名次。学生信息输出函数：按照学生的名次列出每个学生的名次、学号、姓名和成绩。源代码：#include<iostream>usingnamespacestd;#include<stdlib.h>#include<string.h>#defineN7//学生人数；classStudent{public:charxingming[20];intnum;intscore;};intmain(){Studenta[N];cout<<"请输入注册学生的人数："<<N<<endl;for(inti=0;i<N;i++){cout<<"请输入学生的学号、姓名和成绩："<<endl;cin>>a[i].num>>a[i].xingming>>a[i].score;}for(intm=0;m<N;m++){printf("%d%s%d",a[m].num,a[m].xingming,a[m].score);printf("\n");}cout<<"按名次列出学生的学号、姓名、成绩和名次："<<endl;charch[10];for(intq=1;q<N;q++){for(intp=0;p<N-q;p++)if(a[p].score<a[p+1].score){strcpy(ch,a[p].xingming);strcpy(a[p].xingming,a[p+1].xingming);strcpy(a[p+1].xingming,ch);intsc=a[p].score;a[p].score=a[p+1].score;a[p+1].score=sc;intl=a[p].num;a[p].num=a[p+1].num;a[p+1].num=l;}}intb[N];for(intj=1;j<N;j++){b[0]=1;if(a[j].score==a[j-1].score)b[j]=j;elseb[j]=j+1;}for(inti=0;i<N;i++)printf("%d%s%d%d",a[i].num,a[i].xingming,a[i].score,b[i]);printf("\n");}system("PAUSE");}运行结果：编程心得：理解了排序的重要性，也深刻体会到排序在我们周围的广泛应用。通过片成体会到排序的两项基本操作：比较关键字的大小和将记录的位置从一个位置转换到另一个位置。感触尤为深的是C++语言中对象和排序在学生信息系统中的应用，让我感到这些知识的实用性。