西华大学理学院课程设计说明书
1 引 言
1. 1问题的提出
首先，如何产生20000个随机数；其次，对所产生的随机数如何存入文件以方便不同的排序函数所调用；最后，如何处理运用各种排序方法对所产生的随机数进行排序后的结果，并将分析其排序效率。
1.2 C语言
C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。
1.3 C语言发展过程
1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。
1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。
1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming Language》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。
1.4任务与分析
任务是先产生出20000个随机数，然后再实现分别采用快速排序、气泡排序、直接插入排序、归并排序、简单选择排序、堆排序对刚产生的随机数进行排序，并按照要求，需要记录出不同方法排序所花费的时间，所以需要编写一个记录时间的函数模块，在排序开始时调用该函数记录所耗费的时间。
分析：首先，随机数产生的较多时不太好方便操作，于是在写随机数模块时可以先产生较少的随机数进行调试和检查。其次是这学期数据结构这门课中学的排序方法比较多，结合这学期学习的数据结构这门课程，我选择了快速排序、气泡排序、直接插入排序、归并排序、简单选择排序、堆排序这几种排序方式。接着，对随机数采用不同的方式进行排序，想到了将不同的排序方法依次分块写成函数，需要采用哪种方式排序时仅需要调用相应的函数就行了。最后需要记录下不同排序所耗费的时间，就需要再写一个记录耗时的函数了，这样把一个大问题分成若干个小问题，解决起来就简单方便的多了。
2
排序综合
初步想法是利用随机数函数产生20000个随机数，将产生的20000个数放到一个一维数组中，并显示20000个数；设置菜单选项，以选择6种不同的排序方法中的一种进行排序；采用每种排序方法时统计该算法耗时，在屏幕和文件中输出排序结果，之后回到菜单选择界面，然而我又想到不同的排序方式所做出的排序结果不能相互干扰，于是最终我选择将随机数存入文件中，以免排序时混淆。在输出排序结果时我想到不同的排序结果存入不同的文件中，这样结果就简单明了了。
2 系统分析
2.1功能需求
此课题是研究排序综合问题，并用不同的方式对所产生的的2000个随机数进行排序的问题。
确定其主要的几个模块的功能： 1、产生随机数
2、对所产生的随机数进行文件存储 3、用户选择模块
4、不同排序方式调用函数模块 5、文件存储模块 6、计时模块 7、菜单模块
对课题研究的进一步分析，我明确了我需要做的具体步骤：首先需要成功产生随机数，才能继续下一步的运用各种不同的排序方式对随机数进行排序。然后将几种不同的排序方式各自分成一个子快，编写出相应的6个函数（快速排序、冒泡排序、直接插入排序、归并排序、简单选择排序、堆排序），还有一个记录时间的函数模块，然后在主程序里面提示各个选项对相应的功能，用户输入相应的操作数，分别调用不同的函数，打印出相应的排序结果和所耗费的时间。最后，根据调试的结果对各个不同的排序方式加以分析。因此，实际需要设计的服务就是生成随机数，以及不同排序方法的函数编写，以及记录时间的函数的编写，为了直观和方便，画出流程图如下图1：
3
西华大学理学院课程设计说明书
排序综合 耗时函数 图1 程序总的流程图
退出 生成随机数 快速排序 冒泡排序 直接插入排序 归并排序 简单选择排序 堆排序 流程图很直观的描述了整个程序服务过程。
2.1.1总体要求
首先主函数中必须成功生成随机数，在这里我采取了随机种子来达到产生随机数的要求、首先，用户想要对随机数采用不同的方式进行排序，并得到其相应的耗时，就必须按照先序成功创建需要排序的对象即随机数。其次，用户要对随机数进行排序，那就需要知道他想采用的排序方法是什么。这需要用户手动输入选择序号。通过用户输入的信息，计算机就可以进行相关的操作，根据用户输入的信息选择相应的排序方式对所产生的随机数进行排序，输出相应的排序顺序和排序耗时供用户浏览了；我们就要用相应的程序去实现这个过程,这才是我们最后的目的。
4
排序综合
1.4 数据需求
随机产生20000个数
3、详细设计与实现
3.1设计思路
要完成对随机数的排序，有很多种方法可以实现。但是结合自己的知识掌握情况，我选择了比较适合自己的算法，其他的算法还有很多，只是都不是很熟悉，我的思想大多都来源于书上，这学期数据结构所学的排序方法比较多，我选择的有快速排序、冒泡排序、直接插入排序、归并排序、简单选择排序、堆排序。有了上面的分析，下一步自然就是完成分步它的程序了，不能用程序描述出来那在好也没有用的。 3.2详细编码 //包含头文件
#include \#include
//定义的结构体
#define M 2000 //产生随机数个数的定义 const int MAXSIZE=20000; typedef struct{
int key;
}RedType;
5
西华大学理学院课程设计说明书
typedef struct{ RedType r[MAXSIZE+1]; int length; }Sqlist;
typedef Sqlist HeapType; clock_t start,finish; using namespace std;
//自定义函数原型说明
int SelectMin(int a[],int i,int m)//简单选择排序
void Merge (RedType SR[],RedType TR[],int i,int m,int n) //2-路归并排序 int Partition(Sqlist &L, int low, int high)//快速排序 void HeapAdjust(HeapType &H, int s, int m) //堆排序 double duration(clock_t x,clock_t y)//算法耗时统计
//随机数的产生
int i, j, a[M];
char ch;
//定义i,j；待排序数组a[M]; //字符ch,用于记录选项;
srand((unsigned)time(NULL));//设置随机种子; for (i = 1; i < M + 1; i++)
a[i] = rand() % 5000; //随机生成待排序数组a;
cout << \产生20000个随机数\\\\/\system(\
for (i = 1; i < M + 1; i++) //每个元素占6个字符，每行十个元素的格式输出随机生成的待
排序数组a;
{ }
system(\
cout << setw(6) << a[i] << \if (i % 10 == 0)
cout << endl;
经过用户的按键操作，很容易就可以创建出2000个随机数，并弹出菜单项，用户
6