数据结构各种排序算法的课程设计实验报告(c语言版) 下载本文

数据结构各种排序算法的课程设计实验报告(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