内容发布更新时间 : 2024/11/17 3:20:18星期一 下面是文章的全部内容请认真阅读。

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

题目：排序算法的实现与比较

目录

一． 设计内容和要求----------------------------------2 二． 算法思想-------------------------------------------2 三． 程序结构-------------------------------------------3 四． 使用说明-------------------------------------------4 五． 测试结果-------------------------------------------5 六． 收获与体会----------------------------------------6

一． 设计内容和要求

设计内容：排序算法的实现与比较

要求：编程实现希尔、快速、堆排序、归并排序算法，并利用程序统计每种

算法的执行时间。要求随机产生10000、50000、 100000、 200000个待排数据存入磁盘文件，从磁盘文件读入待排数据进行排序，并将排序结果写入另一个文件中。

二． 算法思想

在本课题中，对常见的4 中排序算法希尔、快速、堆排序、归并排序进行实现，并根据待排数据个数的不同来对各种排序算法的执行时间进行比较，从而比较出在不同的情况下各排序算法的性能。 1. 希尔排序

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

先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 2. 快速排序

快速排序是对气泡排序的一种改进，其基本思想是：首先选

一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。 3. 堆排序

堆排序是简单选择排序的一种改进，其基本思想是：首先将待

排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大值即堆顶

记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录。 4. 归并排序

归并排序是一种借助“归并”进行排序的方法，其主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。 5. 计时函数

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

三． 程序结构

说明：本程序由main.cpp,sort.h和operate.h三部分组成。sort.h头文件

中实现了希尔，快速，堆排序，归并排序；operate.h头文件中有随机产生待排数据，将数据写入文件，从文件读数据，计时，输出执行时间的函数；main.cpp主函数调用头文件里的函数。

generate() 随机产生数据函数 operate.h main.cpp read() 文件读取函数 write() 写入文件函数 time() 计时函数 sort.h 4中排序算法的实现函数

文件函数关系表