实验十二 排序算法 (昆工版)

《实验十二 排序算法 (昆工版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2013—2014学年第三学期）课程名称：数据结构开课实验室：信自楼4422013年12月24日年级、专业、班计科122班学号201210405204姓名邹华宇成绩实验项目名称简单的排序算法指导教师胡守成教师评语教师签名：年月日注：报告内容按实验须知中七点要求进行。一、实验目的和要求1.掌握各种查找算法理解和实现；2.增强上机编程调试能力；程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、

2、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。二、实验原理及基本技术路线图（方框原理图）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。-25-（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N

3、-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换。（6）堆排序：在堆排序的算法中先建一个大顶堆

4、，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序。三、所用仪器、材料（设备名称、型号、规格等）联想计算机一台MicrosoftVisualc++6.0四、程序源代码（*cpp）/***********************************************************************

5、***********************排序算法设计要求：利用随机函数产生N个随机整数（N=500，1000，1500，2000，-25-2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、

6、

7、选择排序、堆排序，基数排序七种排序方法************************************************************************************************/#include"stdio.h"#include"stdlib.h

8、"#include"time.h"//计时#defineERROR0#defineOK1#defineOVERFLOW-2#defineMAXSIZE100000//用户自己规定排序的数字的长度typedefintStatus;typedefstruct{int*r;//r[0]闲置intlength;//顺序表的总长度}Sqlist;//构造一个空线性表StatusInitSqlist(Sqlist&L){L.r=(int*)malloc(MAXSIZE*sizeof(int));//分配存储空间if(!L.r){-25

9、-printf("存储分配失败！");exit(0);}//存储分配失败L.length=0;//初始长度为0returnOK;}//输入随机数并显示在界面上StatusScanfSqlist(int&N,Sqlist&L){inti;printf("请输入要排序的元素个数N:");scanf("%d",&N);for(i=1;i<=N;i++)L.r[i]=rand();//随机产生样本整数printf("");printf("随机产生了%d个随机数，它们是：",N);for(i=1;i<=N;i++){pr

10、intf("%7.2d",L.r[i]);}printf("");L.length=N;//存储线性表的长度returnOK;}-25-//输出排序之后的数据StatusPrintfSqlist(intN,SqlistL){inti;printf("数据个数：");//输出数据个数printf("%