数据结构各种排序算法的课程设计实验报告

《数据结构各种排序算法的课程设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告课程名称：数据结构设计题目：排序算法实现及比较系别：计算机信息工程学院专业：计算机科学与技术组别：第*组起止日期:12年5月1日~12年6月1日指导教师:***计算机与信息工程学院二○一二年制课程设计任务书课程设计题目排序算法实现将比较组长***学号20******班级***系别计算机与信息工程学院专业计算机科学与技术组员***指导教师***课程设计目的⑴加深对常见排序算法理解⑵通过程序比较常见算法优越性⑶熟悉加深对数据结构的了解及认识课程设计所需环境Windowsxp；VC++6.0课程设计任务要求⑴实现常见排序算法程序化⑵测试程序比较算法优越性⑶了解常见算法的

2、实际应用课程设计工作进度计划序号起止日期工作内容分工情况1分析实验类容2分工3算法改编成程序4将子程序合并及调试数据测试及记录5编写报告指导教师签字：年月日系（教研室）审核意见：系（教研室）主任签字：年月日目录1.引言42.需求分析43.详细设计43.1直接插入排序43.2折半排序53.3希尔排序63.4简单选择排序63.5堆排序63.6归并排序73.7冒泡排序94.调试105.调试及检验115.1直接插入排序115.2折半插入排序115.3希尔排序125.4简单选择排序125.5堆排序135.6归并排序145.7冒泡排序146.测试与比较156.1调试步骤156.2结论16

3、7.实验心得与分析168.附录178.1直接插入排序178.2折半插入排序188.3希尔排序208.4简单选择排序228.5堆排序238.6归并排序268.7冒泡排序298.8主程序301.引言伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。经常查找资料的朋友都会知道，面对海量的资料，如果其查找的资料没有进行排序，那么其查找资料将会是一件非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。理论上排序算法有很多种，不过本课程设计只涉及到七种算法。这七种算法共包

4、括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。本课程设计通过对这七种算法的运行情况进行对比，选择最优秀的算法来提供给用户。希望通过我们的努力能给用户解决一些问题，带来一些方便。2.需求分析本课程题目是排序算法的实现，由于各方面的原因，本课程设计一共要设计七种排序算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。为了小组分工的方便，我们特意把子函数写成HeaderFile文件。这样操作不仅可以使小组分工更加简洁明了，还可以

5、方便子函数的调用，更可以使写主函数时一目了然。为了运行时的方便，我们将七种排序方法进行编号，其中1为直接插入排序，2为折半插入排序，3为希尔排序，4为简单选择排序，5为堆排序，6为归并排序，7为冒泡排序。通过这七种选项，可以让用户简单明了的去选择使用哪一种排序方法。本课程就是通过对5组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选择面对不同大小的文件时，哪一种算法更为快捷。软件环境本课程设计所用操作系统为Windows-XP操作系统，所使用的软件为MicrosoftVisualC++6.0；3.详细设计3.1直接插入排序⑴算法思想：直接插入排序是一种最简单的

6、排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。⑵程序实现及核心代码的注释：for(i=1;ij;--i)r.base[i]=r.base[i-1

7、];//记录后移r.base[j]=temp;//插入到正确的为位置}r.base[r.length]='';3.2折半排序⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，这般插入排序的时间复杂度仍为O（n2）。⑵程序实现及核心代码的注释：voidzb(FILE*fp){//