《数据结构》课程设计报告和程序代码(2011)

数据结构 课程设计报告

设计题目：排序综合

年 级 三年级 班 级 093班 姓 名 学 号 指导教师 起止时间

2011 年 上 学期

一．实习目的

通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及

操作方法，为进一步的应用开发打好基础。

二．问题描述（具体任务）

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排

序。

要求：

1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希

尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。

2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

3)如果采用4种或4种以上的方法者，可适当加分。 具体任务：

分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题：

1） 建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功

能。并且要求能循环适用系统。

2） 分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。 3） 通过冒泡排序法来测试每组数据用哪种排序算法最优。

三．需求分析

1）本演示程序对以下7种常用的内部排序算法进行实测比较：直接插入排序、

直接选择排序、冒泡排序、快速排序、堆排序、希尔排序、归并排序。

2）

3）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入选择以何种算法进行排序，测试数据可由用户自行输入或由系统产生随机数。每次测试完毕，将显示该排序的排序时间。

4）选择一键排序比较功能，测试完毕，列表显示各种算法的排序时间。并且对结果做出简单分析，给出排序时间最短的两种排序算法。

四．算法设计思想及流程图 五．C语言源代码

#include #include #include

开始 显示菜单 1 直接插入排序 2 直接选择排序 3 冒泡排序 4 快速排序 输入序号 5 堆 排序 6 希尔排序 7 归并 排序 8 一键排序比较 9 显示随机数 0 显示排序后的的数据和时间效率 显示各个排序法对同一组数据排序所用的时间和其中两种较快的方法 退出结束 #include #include #define N 21000

//按键不符时提示 void Wrong() {

printf(\按键错误!\\n\

getchar();//getchar()函数从STDIN(标准输入)获取并返回下一个字符,如果到达文件尾返回EOF }

//显示排序结果

void Disp(int a[]) { int i;

system(\//清屏 for(i=0;i

if((i-1)==9)

printf(\ printf(\ } }

//插入排序

void InsertSort(int a[]) {

int i,j,temp;

for(i=1;i

temp=a[i]; //操作当前元素，先保存在其他变量中

for(j=i;j>0&&a[j-1]>temp;j--) // 从当前元素的上一个元素开始查找合适的位置 a[j]=a[j-1]; a[j]=temp; } }

//选择排序

void SelectSort(int a[]) {

int i,j,k;

for(i=0;i

k=i;

for(j=i+1;j