数据结构实习报告
计 算 科 学 系
数据结构课程设计报
告
设计题目： 内部排序算法的性能分析
系 别： 计算科学系
1
数据结构实习报告
专 业： 信息与计算科学
班 级： 计科
107 （ 1 ）
学生姓名: 陈立荣 学 号: 1074101110
学生姓名: 冯杰 学 号: 1074101112
起止日期: 2008
年
12
月
15
日 ~ 2008
年
1 2
月
19
日
指导教师： 周海岩 冯万利
摘要：
数据结构是计算及程序设计的重要理论基础，它是计算机学科的核心课程，
随着计算机的飞速发展，效率是现在人们所追求的，本次数据结构实习我们所
写的程序就是对数据机构中的几种排序方法做了比较，让我们知道那种排序方
法效率最高!
该程序是在用 C++语言实现的，在程序中随机生成 N 个数据，对这些随机
产生的数据数进行多种方法的排序，所用的这些排序方法都是在数据结构课中
学习过的，比如：冒泡排序、直接插入排序、选择排序 、堆排序、快速排序、
希尔排序等，而且还要对各个排序方法中关键字的比较次数和移动次数做出比
较，即对这几种排序的性能作出分析。
该算法性能比较程序是以读者再提示下输入相应的按键，电脑所产生的结
果显示出来，让读者一目了然，通过屏幕所显示的数据很清楚的知道这几种排
序方法的性能，读者能看出对同一组数据进行排序，不同的排序方法中关键字
所比较的次数和移动的次数，通过这次的实习，我们能对数据结构中几种排序
方法有了进一步的了解！
关键词：冒泡排序、直接插入排序、选择排序 、堆排序、快速排序、希尔排序
2
数据结构实习报告
目 录
摘要 ………………………………………………………………………2
目录 ……………………………………………………………………3
1 需求分析 ………………………………………………………………4
2 概要设计 ………………………………………………………………4
2.1 程序中的一些数据类型定义 ……………………………………4
2.2 设计流程图 ……………………………………………………………5
2.21 集中排序关系图 ……………………………………………………5
2.22 主函数系统流程图 ……………………………………………………5
3 详细设计 ……………………………………………………………………5
3.1 总的函数运行流程图 …………………………………………………6
3.21 插入排序简介及其主要代码 …………………………………………7
3.22 希尔排序简介及其主要代码……………………………………………9
3.23 冒泡排序简介及其主要代码 ……………………………………………10
3.24 快速排序简介及其主要代码…… ………………………………………11
3.25 选择排序简介及其主要代码……………………………………………13
3.26 堆排序简介及其主要代码………………………………………………13
3.3 本程序全部代码清单………………………………………………………15
4 调试与操作说明 …………………………………………………………………… 25
3
数据结构实习报告
4.11 程序运行进入界面 ……………………………………………………25
4.12 程序运行结果界面 …………………………………………………… 25
4.2 调试分析结果 ……………………………………………………………26
5 总结 ………………………………………………………………27
6 致谢 …………………………………………………………………28
参考文献 ………………………………………………………………………29
1 需求分析
(1)本演示程序对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、
堆排序算法进行比较；
(2)待排序表的表长不小于 100，表中数据随机产生，至少用 5 组不同数据作比
较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换
记为 3 次移动）；
(3)输出比较结果。
输入 N 个随机整数，(在该程序中，随机生成的数据个数被初始化为了
150，具有代表意义) 对这些数进行多种方法进行排序，并对这些排序做
比较，在屏幕上输出每种排序方法所比较的次数，交换的次数。
2 概要设计
2.1 程序中的一些数据类型定义
基本操作：
void Suijishu()
{
int i;
srand((int)time( NULL ));
for(i=0; i<MAXSIZE; i++)
RandArray[i]=(int)rand();
4
数据结构实习报告
return;
}
其中 RandomNum（）：产生随机数的函数，利用此函数可以产生随机
数，本程序中利用此函数产生 150 个随机数；
typedef struct StudentData
{
int num;
}Data;
typedef Struct StudentData：定义一个结构体，用于存放关键字或临时
数据等；
typedef struct LinkList
{
int Length; //存放随机数的个数
Data Record[MAXSIZE]; //用数组存放所有的随机数
}LinkList;
typedef struct LinkList：构建一个链表结构体，用于存放随机函数所产
生的随机数；
2.2 设计流程图如下：
2.21 几种排序关系图
5
