七种排序算法的比较及每种排序的上机统计时间

《七种排序算法的比较及每种排序的上机统计时间》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计报告课题:排序算法的比较学院:信息学院班级:2011级电子信息工程1班小组成员:韦志东（组长）20111601310027夏琪20111601310028完成时间:2014-01-08教师:周铁28目录1、课程分析21.1、选题21.2、选题的意义及背景21.3、设计任务书………………………………………………………………22、设计分析22.1、原始数据22.2、输出数据22.3、程序流程图33、程序源代码及注释34、测试结果125、总结266、参考文献277、小组人员分工27281、课程分析1.1、选题要求利用随机函数产生30000个随机整数，利用直接插入排序、希尔排序，冒

2、泡排序、直接选择排序、快速排序、堆排序、归并排序的排序方法进行排序，并统计每一种排序上机所花费的时间。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键词有序的序列。此实验通过对各种内部排序算法进行比较，能使我们更好的掌握各种排序的基本思想，掌握各种排序方法的算法实现，掌握各种排序方法的优劣分析及花费的时间的计算，掌握各种排序方法所适应的不同场合。通过该题目的设计，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能

3、力。1.3、设计任务书（1）定义结构体，头文件，定义数组范围，大小。（2）依次描写七种排序的算法。（3）描写产生随机函数的算法。（4）描写菜单函数。（5）描写主函数，调用七种排序的算法。2、设计分析2.1原始资料用户输入记录的个数30000个，数据由随机函数生成。2.2输出数据产生的随机数分别用冒泡排序、直插排序、希尔排序、选择排序、快速排序、堆排序、归并排序这些排序方法进行排序，并统计每一种排序上机所花费的时间。282.3程序流程图主程序产生1组随机数将随机数保存在数组中二路归并排序冒泡排序直接插入排序堆排序直接选择排序快速排序Shell排序输出排序上机所花费的时间3．程序源代码及其注释#i

4、nclude"stdio.h"#include"stdlib.h"#include"math.h"#include#include#defineMAX60000/*记录数组的个数*/#defineNUM30000/*实际输入数组的个数*/28typedefintdatatype;typedefstruct/*定义记录为结构体类型*/{intkey;/*记录的关键词域*/datatypeother;/*记录的其它域*/}rectype;rectype*s1,s[MAX];/*s[MAX]存放原始随机数，*s1取出原始数据后进行排序*//*直接插入排序算法如下*/

5、voidinsert_sort(rectype*r)/*对数组r按递增顺序进行插入排序算法*/{inti,j,n=NUM;/*NUM为实际输入的记录数，是一个常量*/for(i=1;i<=n;i++)/*i

6、ERTSORT*//*希尔排序算法如下*/voidshell_sort(rectype*r)/*取增量为d(i+1)=[d(i)/2]的希尔排序的算法*/{inti,n,jump,change,temp,m;/*change为交换标志，jump为增量步长*/jump=NUM;n=NUM;/*NUM为顺序表的实际长度*/while(jump>0){jump=jump/2;/*取步长d(i+1)=[d(i)/2]*/do{change=0;/*设置交换标志，change=0表示未交换*/for(i=1;i<=n-jump;i++){m=i+jump;/*取本趟的增量*/if(r[i].key>r[

7、m].key)/*记录交换*/28{temp=r[m].key;r[m].key=r[i].key;r[i].key=temp;change=1;/*change=1表示有交换*/}/*if*/}/*for*//*本趟排序完成*/}while(change==1);/*当change=0时终止本趟排序*/}/*while*//*当增量jump=1且change=0时终止算法*/}/*SHELLSO