数据结构课程设计 排序算法的比较

数据结构课程设计实验报告

南京师范大学

《数据结构》课程设计报告

姓 名：学 院：题 目：指导教师：

学 号： 计算机科学与技术学院 排序算法的实现与比较

2012年9月5日

- 1 -

数据结构课程设计实验报告

目录

一． 设计内容和要求----------------------------------------3

二． 算法思想-----------------------------------------------3

三． 程序结构-----------------------------------------------3

四． 使用说明-----------------------------------------------4

五． 测试结果-----------------------------------------------6

六． 问题以及解决方案---------------------------------------7

七． 收获与体会---------------------------------------------7

八． 参考文献-----------------------------------------------7

- 2 -

数据结构课程设计实验报告

一． 设计内容和要求

设计内容：四种排序算法的实现以及性能比较

要 求：编程实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入磁盘文件，分别采用不同的排序方法进行排序，并将结果存入文件中。

二． 算法思想

在本课题中，我们根据要求对大量的随机数分别使用希尔排序，快速排序，堆排序，归并排序进行排序，并根据随机数数量的增加观察四种排序运行所耗时间，进而分析出四种排序方法在不同情况下的性能好坏。

1. 希尔排序[1]

希尔排序是对直接插入排序的一种改进，它的基本思想是：

先将整个待排序记录序列划分为若干个小序列，在这些小序列中分别进行直接插入排序；逐步扩大小序列的长度，减少小序列的个数，这样使待排序序列逐渐处于更有序的状态；最后对全体序列进行一次直接插入排序，从而完成整个排序过程。

2. 快速排序[2]

快速排序是一个递归的过程，其基本思想是：

从待排序记录中选区一个记录（通常选取第一个记录）为枢轴，其关键字为k，将关键字值小于k的记录移到前面，而将关键字值大于k的移到后面，结果将待排序记录序列分成两个子表，最后将关键字值为k的记录插到分界线处，我们将这个过程成为“划分”，对划分后的子表继续按上述原则进行划分，直到所有子表不超过1为止，此时待排序记录序列就编程了一个有序序列。

3. 堆排序[3]

堆排序是选择排序的一种改进，其基本思想是：

首先用待排序的记录序列构造成一个堆，此时选出堆中所有记录的最大者，即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录为止。

4. 归并排序[4]

归并排序是通过“归并”进行排序的一种方法。归并就是将两个或两个以上的有序序列合并成一个有序序列的过程。其基本思想是：

将若干有序序列逐步归并，最终归并为一个有序序列。

5. 计时函数

计时函数使用了高精度时间函数QueryPerformanceFrequency()和QueryPerformanceCounter()来实现毫秒级的计时功能。该函数接受一个指向函数的指针参数，用于在两次查询机器内部计时器的位置插入所需要被计时的代码，再将两次查询之差除以CPU 时钟频率即可得到事件执行的精确时间。

三． 程序结构

说 明：本程序由main.cpp、sort.h和operate.h三部分组成。Sort.h头文件中实现了希尔排序，快速排序，堆排序以及归并排序这四种排序；operate.h头文件中实现了产生随机待排数据，将数据写入文件，从文件读数据，计算排序所消耗时间，以及输出执行时间的功能；main.cpp主函数负责提示操作以及调用头文件里的函数。

- 3 -

数据结构课程设计实验报告

生成随机数 存入文件

main.cpp operate.h 计算耗时 写入文件 ShellSort HeapSort sort.h QuickSort

程序结构分析图

MergeSort

四． 使用说明

首先，运行程序，出现如下界面，提示用户按照步骤操作，从1到4依次逐步执行；

进入程序后首先根据提示，1.产生大量随机待排序数据，这个数据是需要存到名为a的文本文件中的；

随机待排序数据已经产生，下面按照要求将待排序数据写入磁盘文件，这个步骤是必须的，写入文本文件后，还是要从文本文件中读取到内存中，继而进行下一步操作；

接下来就是对大量的待排序数据进行排序以及计时，一开始的代码是将计时函数写成int型的返回值的，但是后来发现int型的在处理较小数量的排序时，体现不出四种排序的差异，所以之后将计时函数写成double型的返回值，这样即使在整数部分相同的情况下，也能比较出四种排序的优劣；

- 4 -