1、 数据结构课程设计实验报告数据结构课程设计实验报告 题目：排序算法的实现与比较题目：排序算法的实现与比较 目录目录 一一 设计内容和要求设计内容和要求-2 二二 算法思想算法思想-2 三三 程序结构程序结构-3 四四 使用说明使用说明-4 五五 测试结果测试结果-5 六六 收获与体会收获与体会-6 一一设计内容和要求设计内容和要求 设计内容：设计内容：排序算法的实现与比较 要求要求：编程实现希尔、快速、堆排序、归并排序算法，并利用程序统计每种 算法的执行时间。要求随机产生 10000、50000、 100000、 200000 个待排数 据存入磁盘文件，从磁盘文件读入待排数据进行排序，并将排序
2、结果写入另 一个文件中。 二二算法思想算法思想 在本课题中，对常见的4 中排序算法希尔、快速、堆排序、归并排序进行 实现，并根据待排数据个数的不同来对各种排序算法的执行时间进行比较， 从而比较出在不同的情况下各排序算法的性能。 1. 希尔排序 希尔排序是对直接插入排序的一种改进，它的基本思想是： 先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插 入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 2. 快速排序 快速排序是对气泡排序的一种改进，其基本思想是：首先选 一个轴值（即比较的基准） ，将待排序记录分割成独立的两部分，左侧记录的 关键码均小于或等于轴值，右
3、侧记录的关键码均大于或等于轴值，然后分别 对这两部分重复上述过程，直到整个序列有序。 3. 堆排序 堆排序是简单选择排序的一种改进，其基本思想是：首先将待 排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大值即堆顶 记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换） ，并 将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中 只有一个记录。 4. 归并排序 归并排序是一种借助“归并”进行排序的方法，其主要思想是：将 若干有序序列逐步归并，最终归并为一个有序序列。 5. 计时函数 计时函数使用了Windows API 函数QueryPerformanceFrequency 和 QueryPerformanceCounter 来实现毫秒级的计时功能。该函数接受一个指向 函数的指针参数，用于在两次查询机器内部计时器的计插入所需要被计时的 代码，再降两次查询之差除以CPU 时钟频率即可得到事件执行的精确时间。 三三程序结构程序结构 说明：说明：本程序由 main.cpp,sort.h 和 operate.h 三部分组成。sort.h 头文件 中实现了希尔，快速，堆排序，归并排序；operate.h 头文件中有随机产生 待排
