《数据结构》课程设计报告学生姓名:学号：
学院: 理学院
班级:
题目: 题目33 排序综合
指导教师：职称:讲师
实验师
讲师
2012年12月28日
目录
目录 .......................................... I
一、选题背景 (1)
1.1 背景 (1)
1.2 摘要 (1)
1.3 性能比较.............................................. 错误!未定义书签。
1.4 总体框架 (2)
1.5 操作函数说明 (2)
二、算法设计 (3)
2.1 插入排序 (3)
2.2 希尔排序 (3)
2.3 折半插入排序 (4)
2.4 冒泡排序 (4)
2.5 快速排序 (4)
2.6 简单选择排序 (5)
2.7 归并排序 (5)
三、程序及功能说明 (6)
3.1 随机数生成函数 (6)
3.2 文件的存储与读取 (6)
3.3 插入排序 (7)
3.4 希尔排序 (8)
3.5 折半插入排序 (9)
3.6 冒泡排序 (9)
3.7 快速排序 (10)
3.8 简单选择排序 (11)
3.9 归并排序 (12)
3.10 退出函数 (13)
3.11 菜单函数 (14)
四、结果分析 (18)
4.1 操作说明 (18)
4.2 运行时间 (22)
五、总结 (26)
六、课程设计心得体会 (27)
参考文献 (30)
源程序 (31)
文件内容 (43)
一、选题背景
1.1 摘要
该课程设计的主要内容是：设计一个对生成的随机数进行综合排序的程序，进行九种排序算法，并计算时间复杂度，选出两种较快的方法。
九种排序算法分别是：直接插入排序、希尔排序、折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序。将随机生成的数写入文件中，打开文件，则可通过不同的方法进行排序。
另外该程序还具备界面选择输入输出、文件读写等功能。该程序还可以由用户自己设定随机数的个数与范围以及生成随机数文件的路径，设定每种排序算法的排序个数。在综合排序这个功能中，还将每种排序算法所用时间写入到了指定文件中。
1.2 背景
在学习了数据结构中排序一章节时，各种排序方法让人打开编程的视野。借这次课程设计的机会，来更深入的了解排序，对随机生成的大量数据进行排序，并比较他们之间的优劣性，找出在这种情况下最适合的排序方法。
1.3 性能比较
以计算花费的时间为准进行对比，选出两种较快的排序算法。以此分析在每种存储结构的下九种排序算法的优劣，输出每种算法的所用时间。并且每种排序算法所用的时间结果都能保存到指定文件中。
每种排序算法的输入数据都由产生的随机数文件中读取。排序的个数可以由用户定义。每种排序算法的结果都能正确的保存到相应的TXT文件中，如插入排序算法的结果保存到“插入排序算法.txt”文件中。
经过查资料，可知：排序的个数不适合过大，要求一般在20，000左右就能得出正确结果。顺序表存储结构的排序个数不应超过200，000个，一般在200，000左右也能分出结果。
综上所述总结出自己的设计思路：
（1）由用户选择要排序的数据的数目和范围，规定为20,000~200，000个，其数据是随机产生的。
（2）进入选择界面，由用户选择要进行的排序算法，选择是否调用随机数生成函数并将结果保存在文件中。进行排序时，选择打开只输出在这两种
存储结构下的排序所花费时间用于比较。综合排序时，要比较出两种较快排序，输出结果，并将所有排序所花费的时间全部写入指定文件。
1.4 总体框架
图1 总体架构图
1.5 操作函数说明
void creat()：定义随机函数，产生随机数据
void save(int f1[])：保存文件
void read()：读取文件
void DirectInsertSort(int p[], int len)：直接插入排序
void ShellSort(int a[],int n)：希尔排序
void BinSort(int r[],int length)：折半插入排序
void sort(int a[N],int n)：冒泡排序
int my_quick(int a[],int low,int high)：定义快速排序函数
void buuble(int a[],int n)：简单选择排序
void merge(int a[N],int l_start,int l_end,int r_end)：归并排序1
int msort(int a[N],int start,int end)：归并排序2
void end()：定义结束函数
void menu()：函数声明//控制输出格式
void display(int a[],int n)：菜单函数
void menu()：菜单函数
二、算法设计
2.1直接插入排序
第1遍，将初始文件中的记录K1看作有序子文件，将K2插入这个子文件中。若R2的关键字小于K1的关键字，则R2插在K1的前面，否则K2插在K1的后面。第2遍，将K3插入前面的两个记录的有序子文件中，得到3个记录的有序子文件。依此类推，继续进行下去，直到将Kn插入到前面的n-1个记录的有序子文件中，最后得到n个记录的有序文件。
下面是我举的一个直接插入排序的例子。
K0 K1 K2 K3 K4 K5
初始关键字： 43 21 89 15 43 28
第一遍排序后：21 ( 21 43 ) 89 15 43 28
第二遍排序后：89 ( 21 43 89 ) 15 43 28
第三遍排序后：15 ( 15 21 43 89 ) 43 28
第四遍排序后：43 ( 15 21 43 43 89 ) 28
第五遍排序后：28 ( 15 21 28 43 43 89 )
2.2希尔排序
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2（1）取一组数据（9,3,5,1,6,2,8,4,7）
（2）取增量为5
则分为五个组（9，2）（3，8）（5，4）（1，7）（6），对这些分组内部进行插入排序，
得到：2，3，4，1，6，8，5，7，9
（3）取增量为3
