数据结构课程设计报告

《数据结构》课程设计 实验报告 题 目 内部排序算法的的性能分析 学 院 数理与信息工程学院 专 业 计算机科学与技术 班 级 计科学122班 学 号 201259225236 学生姓名 黄文财 同组成员 金坚扬 李嘉良 指导教师 朱蓉 编写日期 2014.06.29

1 问题描述

设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果。

2 问题分析

（1）用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。

（2）利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。

（3）在主函数中调用用户自定义函数，输出比较结果。

（4）本程序是对几种内部排序算法的关键字进行性能分析的程序，它分为以下几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。

3 数据结构描述

3．1抽象数据类型定义

Insertsort();

初始条件：数组已经存在。

基本思想：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。

Shellsort();

初始条件：数组已经存在。

基本思想：先取定一个正整数d1

d1倍数的记录放在一组中，在各组内进行插入排序，然后取d2

组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。

Bubblesort();

初始条件：数组已经存在。

基本思想：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。

QuickSort(int low,int high)；

初始条件：数组已经存在。

基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的安置在一部分，所有键值比它大的安置在另一部分，并把该记录排在两部分的中间，也就是该记录的最终位置。这个过程称为一趟快速排序。然后分别对所划分的两部分重复上述过程，一直重复到每部分内只有一个记录为止排序完成。

Selectsort();

初始条件：数组已经存在。

基本思想：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完。对待排序的文件进行n-1趟扫描，第i趟扫描选出剩下的n-i+1个记录，并与第i个记录交换。

3．2模块划分

本程序包括两个模块： （1）主程序模块

void main() {

初始化； 随机数的产生； 调用子函数

}；

（2）子函数模块：实现直接插入排序的抽象数据类型。 实现希尔排序的抽象数据类型 实现冒泡排序的抽象数据类型 实现快速排序的抽象数据类型 实现选择排序的抽象数据类型

实现5种排序数据对比 实现数据的更换 实现表长的更改

最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数（关键字的交换记为三次移动），与所费时间。从而直观的判断各内部排序算法性能的优劣性。

4．主要模块的算法描述 数据类型的定义

(1)直接插入排序类型：

void Insertsort();

(2)希尔排序类型：

void Shellsort();

(3)冒泡排序类型：

void Bubblesort();

(4)快速排序类型：

void QuickSort(int low,int high);

(5)选择排序类型：

void Selectsort();

(6) 5种排序数据对比：