数据结构各种排序算法的课程设计实验报告(c语言版)
滁州学院
课程设计报告
课程名称： 数据结构
设计题目： 排序算法实现及比较
系 别： 计算机信息工程学院
专 业： 计算机科学与技术 组 别： 第*组 起止日期: 12 年 5 月 1 日 ~ 12 年 6月 1 日 指导教师: ***
计算机与信息工程学院二○一二年制
1 / 33
数据结构各种排序算法的课程设计实验报告(c语言版)
课程设计任务书
课程设计题目 组长 系别 *** 计算机与信息工程学院 排序算法实现将比较 学号 专业 20****** 班级 *** 计算机科学与技术 组员 *** 指导教师 *** ⑴加深对常见排序算法理解 ⑵通过程序比较常见算法优越性 ⑶熟悉加深对数据结构的了解及认识 Windows xp；VC++6.0 ⑴实现常见排序算法程序化 ⑵测试程序比较算法优越性 ⑶了解常见算法的实际应用 课程设计工作进度计划 序号 1 2 3 4 5 指导教师签字： 年 月 日 起止日期 工 作 内 容 分析实验类容 分工 算法改编成程序 将子程序合并及调试 数据测试及记录 分工情况 编写报告 课程设计目的 课程设计所需环境 课程设计任务要求 系（教研室）审核意见： 系（教研室）主任签字： 年 月 日 2 / 33
数据结构各种排序算法的课程设计实验报告(c语言版)
目 录
1.引言 .............................................................................................................................................................. 4 2.需求分析 ...................................................................................................................................................... 4 3.详细设计 ...................................................................................................................................................... 4
3.1 直接插入排序 .................................................................................................................................. 4 3.2折半排序 ........................................................................................................................................... 5 3.3 希尔排序 .......................................................................................................................................... 6 3.4简单选择排序 ................................................................................................................................... 6 3.5堆排序 ............................................................................................................................................... 6 3.6归并排序 ........................................................................................................................................... 7 3.7冒泡排序 ........................................................................................................................................... 9 4.调试 ............................................................................................................................................................ 10 5.调试及检验 ................................................................................................................................................ 11
5.1 直接插入排序 ................................................................................................................................ 11 5.2折半插入排序 ................................................................................................................................. 11 5.3 希尔排序 ........................................................................................................................................ 12 5.4简单选择排序 ................................................................................................................................. 12 5.5堆排序 ............................................................................................................................................. 13 5.6归并排序 ......................................................................................................................................... 14 5.7冒泡排序 ......................................................................................................................................... 14 6.测试与比较 ................................................................................................................................................ 15
6.1调试步骤 ......................................................................................................................................... 15 6.2结论 ................................................................................................................................................. 16 7.实验心得与分析 ........................................................................................................................................ 16 8.附录 ............................................................................................................................................................ 17
8.1直接插入排序 ................................................................................................................................. 17 8.2折半插入排序 ................................................................................................................................. 18 8.3希尔排序 ......................................................................................................................................... 20 8.4简单选择排序 ................................................................................................................................. 22 8.5堆排序 ............................................................................................................................................. 23 8.6归并排序 ......................................................................................................................................... 26 8.7冒泡排序 ......................................................................................................................................... 29 8.8主程序 ............................................................................................................................................. 30
3 / 33
数据结构各种排序算法的课程设计实验报告(c语言版)
1.引言
伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战。
经常查找资料的朋友都会知道，面对海量的资料，如果其查找的资料没有进行排序，那么其查找资料将会是一件非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。 理论上排序算法有很多种，不过本课程设计只涉及到七种算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。
本课程设计通过对这七种算法的运行情况进行对比，选择最优秀的算法来提供给用户。希望通过我们的努力能给用户解决一些问题，带来一些方便。
2.需求分析
本课程题目是排序算法的实现，由于各方面的原因，本课程设计一共要设计七种排序算法。这七种算法共包括：直接插入排序，折半插入排序，希尔排序，简单选择排序，堆排序，归并排序，冒泡排序。七种排序各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。
为了小组分工的方便，我们特意把子函数写成Header File文件。这样操作不仅可以使小组分工更加简洁明了，还可以方便子函数的调用，更可以使写主函数时一目了然。
为了运行时的方便，我们将七种排序方法进行编号，其中1为直接插入排序，2为折半插入排序，3为希尔排序，4为简单选择排序，5为堆排序，6为归并排序，7为冒泡排序。通过这七种选项，可以让用户简单明了的去选择使用哪一种排序方法。
本课程就是通过对5组占用内存大小不同的数据调试来测试这七种算法运行的时间长短，从中选择面对不同大小的文件时，哪一种算法更为快捷。
软件环境本课程设计所用操作系统为Windows-XP操作系统，所使用的软件为Microsoft Visual C++ 6.0；
3.详细设计
3.1 直接插入排序
⑴算法思想：直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增一的有序表。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 ⑵程序实现及核心代码的注释：
for (i = 1 ; i < r.length ;++i )
for(j=0;j < i;++j) if(r.base[i] < r.base[j])
4 / 33
数据结构各种排序算法的课程设计实验报告(c语言版)
{ }
r.base[r.length] ='\\0';
temp = r.base[i]; //保存待插入记录 for(i= i ;i > j; --i )
r.base[i] = r.base[i-1]; //记录后移
r.base[j] = temp; //插入到正确的为位置
3.2折半排序
⑴算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，这般插入排序仅减少了关键字间的比较次数，而记录的移动次数 不变。因此，这般插入排序的时间复杂度仍为O（n2）。 ⑵程序实现及核心代码的注释： void zb(FILE *fp)
{ //对顺序表作折半插入排序
for ( i = 1 ; i < r.length ; i++ ) {
temp=r.base[i]; //将r.base[i]寄存在temp中 low=0; high=i-1;
while( low <= high ) //在base[low]到key[high]中折
半查找有序插入的位置
}
{ }
for( j=i-1; j>=high+1; --j )
r.base[j+1]= r.base[j];
//记录后移
m = (low+high)/2; //折半 if ( temp < r.base[m] ) else
low = m+1; //插入高半区 high = m-1; //插入低半区
r.base[high+1]=temp; //插入
5 / 33