北邮数据结构实验四.pdfVIP

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称：实验四排序——题目一

学生姓名：

班级：

班内序号：

学号：

日期：2012年12月15日

1．实验要求

使用简单数组实现下面各种排序算法，并进行比较。

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2.程序分析

首先，题目要求测试不同的数据，所以可以手动输入待排序元素。其次，由于对一组数据要求用不同的排序算

法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。再次，由于每次排序后都

需要把排序后的结果打印出来，代码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打

印函数。最后，由于题目中要求计算代码的执行时间精确到微妙级，而c++库函数中的clock（）函数等只能精确

到毫秒级，故需调用微软公司在其多媒体Windows中提供了精确定时器的底层API支持，本实验中调用

queryperformancefrequency和queryperformancecounter函数即可满足精确到微妙级的要求。

2.1存储结构

本程序采用简单数组来储存输入的待排序数组。

第1页

北京邮电大学信息与通信工程学院

2.2关键算法分析

2.2.1插入排序算法

插入排序的思想是：每次从无序区取一元素将其添加到有序区中。

C++描述如下，其中形参r[]为待排序数组，n为待排序元素个数

2.2.2希尔排序算法

希尔排序是一种缩小增量排序的算法，首先将待排序元素集按照一定间隔分成多个子集，分别对这些子集进

行直接插入排序，整个序列部分有序。然后缩小间隔，在进行直接插入排序，直到间隔为1，此时，整个序列已全

部有序。其c++描述如下：

第2页

北京邮电大学信息与通信工程学院

2.2.3冒泡排序

冒泡排序的思想是：两两比较相邻的元素，如果反序，则交换次序，直到没有反序的元素为止。

在此思想指导下①首先将待排序元素划分为有序区和无序区，初始状态有序区为空，无序区所有待排序素；

②对无序区从前向后依次将相邻元素关键码进行比较，若反序，则交换

③重复执行②直到无序区中没有元素。

第3页

北京邮电大学信息与通信工程学院

2.2.4快速排序算法

2,2,4,1一趟快速排序算法自然语言描述如下

①选取区间第一个元素作为轴值

②读取区间首尾坐标，并将其左右侧待比较元素

③右侧扫描：从后向前找到第一个比轴值小的元素，和左侧待比较元素交换（左侧第一个带比较元素为轴值）

④左侧扫描：从前向后找到第一个比轴值大的元素，和右侧待比较元素交换

⑤重复②③，直到左右两侧带比较元素的坐标相等

其c++描述如下

第4页

北京邮电大学信息与通信工程学院

2.2.4.2完整的快速排序算法如下：

2.2.5选择排序算法

选择排序自然语言描述如下：

①在r[1]~r[n]待排序元素序列中选出最小记录，将其与第一个元素r[n]交换

②在r[2]~r[n]待排序元素序列中选出最小记录，将其与第一个元素r[i]交换

…………

③直至r[n-1]~r[