文档介绍：师大学
《数据结构》
课程设计报告
：
学号：
院系：计算机学院软件工程
班级：
指导教师：
目录
《数据结构》课程设计报告 1
一、必做题 2
Ⅰ、设计容和要求 2
Ⅱ、算法思想 2
Ⅲ、程序结构 2
Ⅳ、使用说明 2
Ⅴ、测试结果 2
Ⅵ、问题以及解决方案 2
Ⅶ、收获与体会 2
Ⅷ、参考文献 2
二、选做题 2
㈠、设计容和要求 2
㈡、算法思想 2
㈢、程序结构 2
㈣、测试结果 2
㈤、收获与体会 2
一、必做题
Ⅰ、设计容和要求 
设计容：四种排序算法的实现以及性能比较 
要求：编程实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进行排序，并将结果存入文件中。
Ⅱ、算法思想 
在本课题中，我们根据要求对大量的随机数分别使用希尔排序，快速排序，堆排序，归并排序进行排序，并根据随机数数量的增加观察四种排序运行所耗时间，进而分析出四种排序方法在不同情况下的性能好坏。 
1. 希尔排序
希尔排序是对直接插入排序的一种改进，它的基本思想是： 
先将整个待排序记录序列划分为若干个小序列，在这些小序列中分别进行直接插入排序；逐步扩大小序列的长度，减少小序列的个数，这样使待排序序列逐渐处于更有序的状态；最后对全体序列进行一次直接插入排序，从而完成整个排序过程。 
2. 快速排序
快速排序是一个递归的过程，其基本思想是： 
从待排序记录中选区一个记录（通常选取第一个记录）为枢轴，其关键字为k，将关键字值小于k的记录移到前面，而将关键字值大于k的移到后面，结果将待排序记录序列分成两个子表，最后将关键字值为k的记录插到分界线处，我们将这个过程成为“划分”，对划分后的子表继续按上述原则进行划分，直到所有子表不超过1为止，此时待排序记录序列就编程了一个有序序列。 
3. 堆排序
堆排序是选择排序的一种改进，其基本思想是： 
首先用待排序的记录序列构造成一个堆，此时选出堆中所有记录的最大者，即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录为止。 
4. 归并排序
归并排序是通过“归并”进行排序的一种方法。归并就是将两个或两个以上的有序序列合并成一个有序序列的过程。其基本思想是： 
将若干有序序列逐步归并，最终归并为一个有序序列。 
5. 计时函数 
计时函数使用了高精度时间函数QueryPerformanceFrequency()和QueryPerformanceCounter()来实现毫秒级的计时功能。该函数接受一个指向函数的指针参数，用于在两次查询机器部计时器的位置插入所需要被计时的代码，再将两次查询之差除以CPU 时钟频率即可得到事件执行的精确时间。
Ⅲ、程序结构
、。，快速排序，堆排序以及归并排序这四种排序；，将数据写入文件，从文件读数据，计算排序所消耗时间，以及输出执行时间的功能；。
Ⅳ、使用说明
首先，运行程序，出现如下界面，提示用户按照步骤操作，从1到4依次逐步执行
❶
❷
❸
❹
❺
Ⅴ、测试结果
未完成排序的待排数据已经存入名为a的文本文档中.
已完成排序的待排数据已经存入名为b的文本文档中.
Ⅵ、问题以及解决方案 
本题的难点在于文件的读写和时间的计算。所以，我首先通过书籍和网络复****和查阅这两个方面的相关资料，结合自己已经学过的或者编写过的程序来完成这个题目。
Ⅶ、收获与体会
通过这次的课程设计，让我对希尔排序，快速排序，堆排序以及归并排序有写代码的过程中，遇到了一些头疼的问题，比如将数据结构课程设计实验报告