排序算法的实现

《排序算法的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、附件2：北京理工大学珠海学院实验报告ZHUHAICAMPAUSOFBEIJINGINSTITUTEOFTECHNOLOGY班级学号姓名指导教师成绩实验题目排序算法的实现实验时间一、实验目的、意义（1）掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识（2）掌握Shell排序的的基本思想和算法实现（3）掌握快速排序的基本思想和算法实现（4）掌握选择排序中堆排序的基本思想和算法实现（5）了解归并排序算法的基本思想和程序实现二、实验内容及要求说明1：学生在上机实验时，需要自己设计出所涉及到的函数

2、，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：本实验含有四部分内容——直接插入排序、希尔排序、选择排序、快速排序，在上述内容的基础上，将所有排序算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路，新算法。1.考虑对20个整数的随机输入进行排序，各排序功能基本上都可以成为独立调用的模块，因此可以先写出排序算法，然后用主函数调用。三、实验所涉及的知识点本实验涉及各类排序算法。Shel

3、l排序：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量重复上述分组和排序，直至所取的增量dt=1(dt

4、导致了各种算法的混乱，加上书本上的伪代码，在调试过程中，寻求了同学的帮忙和借阅同学的代码才得以完成这次实验。9五、实验结果及分析（1）插入排序；（2）希尔排序；9（1）选择排序中的堆排序；（4）快速排序；六、总结与体会直接插入排序属于稳定的排序，快速排序属于不稳定排序，希尔排序属于不稳定排序，堆排序属于不稳定排序。通过这次排序算法的实验，虽然算法只是按照书本上的算法，但总算对于各种算法有了大致的了解。9七、程序清单(包含注释)#include#include//函数

5、结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASLIBLE-1#defineOVERFLOW-2#defineMAXSIZE20//一个用作示例的小顺序表的最大长度#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))//-----------存储结构----------typedefintKeyType;//定义关键字类型为整数类

6、型typedefintStatus;typedefintElemType;typedefstruct{KeyTypekey;//关键字项//InfoTypeotherinfo;//其他数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表的长度}SqList;//顺序表类型//-----------基本操作的函数实现-------------StatusInitSqList(SqList*L){

7、//构造一个空的线性表Linti;for(i=0;i<=MAXSIZE;i++){L->r[i].key=0;}L->length=0;9returnOK;}//InitListStatusInsertSqList(SqList*L,KeyTypenum){//将num插入到顺序表L中L->length+=1;L->r[L->length].key=num;returnOK;}//InsertSqListvoidInsertSort(SqList*L){//对顺序表L作直接插入排序inti,j;for(

8、i=2;i<=L->length;i++){if(LT(L->r[i].key,L->r[i-1].key)){//"<"，需要将L->r[i]插入有序子表L->r[0]=L->r[i];//复制为哨兵L->r[i]=L->r[i-1];for(j=i-2;LT(L->r[0].key,L->r[j].key);j--)L->r[j+1]=L->r[j];//记录后移L->r[j+1]=L->r[0];//插入到正确位置}}}//Inser