选题：希尔、快速、堆排序、
归并排序算法
姓名：顾敏
学号： 19110233
目录
一．题目描述
编程实现希尔、快速、堆排序、归并排序算法。

要求随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进行排序，并将结果存入文件中。

二．算法思想描述
1.读写文件：
（1）以磁盘文件为对象进行输入输出，用于文件操作的文件类有:
ifstream类，它是从istream类派生的。

用来支持从磁盘文件的输入。

ofstream类，它是从ostream类派生的。

用来支持向磁盘文件的输出。

（2）打开文件包括:
(1) 为文件流对象和指定的磁盘文件建立关联，以便使文件流流向指定的
磁盘文件。

一. 调用文件流的成员函数open。

如：
ofstream outfile;//定义ofstream类(输出文件流类)对象outfile
outfile.open(″f1.dat″,ios::out); //使文件流与f1.dat文件建立关联
二．在定义文件流对象时指定参数
在声明文件流类时定义了带参数的构造函数，其中包含了打开磁盘文件的
功能。

因此，可以在定义文件流对象时指定参数，调用文件流类的构造函
数来实现打开文件的功能。

如：
ostream outfile(″f1.dat″,ios::out);
（4）关闭文件用成员函数close。

如：
outfile.close( );//将输出文件流所关联的磁盘文件关闭
（5）对ASCII文件的读写操作可以使用: 流插入运算符“<<”和流提取运算符“>>”输入输出标准类型的数据。

2.随机数的产生：
（1）首先应在开头包含头文件stdlib.h
（2）rand()函数没有输入参数，直接通过表达式rand()来引用。

为了使程序在每次执行时都能生成一个新序列的随机值，通常通过为随机数生成器提
供一粒新的随机种子。

函数srand()(来自stdlib.h)可以为随机数生成器播
散种子。

只要种子不同rand()函数就会产生不同的随机数序列。

srand()
称为随机数生成器的初始化器。

（3）rand()产生伪随机数，srand函数提供种子，种子不同产生的随机数序列也不同，所以通常先调用srand函数time(0)返回的是系统的时间（从
1970.1.1午夜算起），单位：秒，种子不同当然产生的随机数相同几率就
很小。

3.希尔排序：
按一定的间隔将表分成若干子表,每个子表分别进行插入排序。

希尔排序是一种不稳定的排序方法。

4.快速排序：
取待排序列中某个元素的值作为基准值，将待排序列划分为两个部分，左
边部分的所有元素都小于等于这个基准值，而右边部分的所有元素都大于等于
这个基准值。

然后,对左右两个子表用同样的方法(递归)进行划分。

快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n*n)；最好时间复杂度为O(nlog2n)。

可以证明，快速排序的平均
时间复杂度也是O(nlog2n)。

快速排序是不稳定的排序方法。

5.堆排序：
堆排序的过程是（1）将无序序列建成一个堆。

（2）输出堆顶元素，将剩余元素调整为一个新堆。

堆排序的第一个工作是建堆，即把整个记录数组r[1]到r[n]调整为一个堆。

显然,只有一个结点的树是堆，而在完全二叉树中，所有序号i >= low(n/2)
的结点都是叶子，因此以这些结点为根的子树都已是堆。

这样，我们只需依次
将序号为low(n/2)，low(n/2)-1，...，1的结点作为根的子树都调整为堆即
可。

堆排序的时间复杂性为O(n log2n) 。

堆排序空间复杂性为 O(1)。

堆排序是不稳定的排序方法。

6.归并排序：
归并排序就是利用“二路归并”操作实现排序的。

其基本思想是：将待排序列r[0]到r[n-1]看成n个长度为1的有序子序列，把这些子序列两
两归并，便得到(n/2)个有序的子序列。

然后再把这(n/2)个有序的子序列两两
归并，如此反复，直到最后得到一个长度为n的有序序列。

归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做(log2n)趟归并，每趟归并所花的时间为O(n)。

所以，二路归并排序算法的时间复杂度为O (n log2n)，辅助数组所需的空间
为O(n)。

归并排序是稳定的排序方法。

三．程序结构
1.读写文件的函数模块：
将随机数存入目标文件：void File(char filepath[])
将结果写入文件中：void WriteFile(char filepath[],int data[])
从文件中读取数据：void ReadFile(char filepath[],int data[])
2.排序的函数模块：
快速排序模块：
堆排序模块：
归并排序模块：
3.各模块之间的关系：
四．测试结果
（1）初始页面：
（2）进行希尔，快速，堆，归并排序，分别存放在文件中：
（3）返回重新输入存放随机数的文件：
（4）排序结果对比：
五．收获与体会
在课程设计中，遇到的主要难点是对于文件的操作，在查找了有关C++文件操作的资料以后，我对文件的操作更加熟练。

其次，在写快速排序、归并排序和堆排序时通过对代码的理解，加深了自己有关这几种排序的影响，不仅仅停留在用画图或者书面上的理解的基础上。