1、排序综合课程设计.大连科技学院数据结构课程设计题 目 排序综合学生 专业班级指导教师 职 称 副教授所在单位 信息科学系软件教研室教学部主任完成日期 2013 年1月11 日.课程设计报告单学号 专业班级 网络工程 11-1考 核 项 目 评分 备注平时工作态度及遵守纪律情况1（10 分）掌握基本理论、关键知识、基本技能的程度和2阅读参考资料的水平（10 分）独立工作能力、综合运用所学知识分析和解决3问题能力及实际工作能力提高的程度（20 分）完成课程设计说明书及软件的情况与水平（小组分工情况、规性、整洁清楚、叙述完整性、4思路清晰程度、工作量及实际运行情况和创新性）（60 分）总评成绩综 合
2、 评 定： （优、良、中、及格、不及格）.指导教师签字：2013年1月11日数据结构课程设计任务书一、任务及要求：1.设计（研究）任务和要求研究容：排序综合任务和要求：（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。（2）对指导教师下达的题目进行系统分析。（3）根据分析结果完成系统设计。（4）编程：在计算机上实现题目的代码实现。（5）完成对该系统的测试和调试。（6）提交课程设计报告。要求完成课程设计报告 3000 字以上 (约二十页 )。完成若干综合性程序设计题目，综合设计题目的语句行数的和在 100 行语句以上。2.原始依据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻
3、辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3.参考题目：二、工作量2 周（ 10 个工作日）时间三、计划安排第 1 个工作日：查找相关资料、书籍，阅读示例文档，选择题目。第 2 个工作日第 3 个工作日：设计程序结构、模块图。第 4 个工作日第 9 个工作日：完成程序的编码，并且自己调试、测试。穿插进行课程设计报告的撰写。第 10 个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生成绩。指导教师签字：2012年12月
4、24日.排序综合 11.需求分析 11.1 任务描述 11.2 功能分析 12.概要设计 12.1 主要全程变量和数据结构 12.2 程序模块结构 23.详细设计 33.1 程序的主要结构如下图所示。 33.3 显示各排序算法排序后的的数据。 43.4 函数实现（例如直接插入排序） 44.调试分析 55.测试结果及运行效果 7参考文献 11附录 全部代码 12数据结构课程设计总结 24.排序综合1.需求分析1.1 任务描述至少采用 3 种方法实现上述问题求解，并把排序后的结果保存在不同的文件中。1.2 功能分析显示随机数 ，是调用 rand() 函数输出数组 a。数组 a中保存有随机产生的随机
5、数； 直接选择排序 ，是通过 n-1 次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i 个记录交换之； 起泡排序 ，是如果有 n 个数，则要进行 n-1 趟比较，在将整个待排记录序列分割成为若干子序列分别进行直接插入排序， 待整个排序中的记录“基本有序 ”时，在对全体记录进行一次直接插入排序； 直接插入排序 ，是将一个记录插入到以排序好的有序表中， 从而得到一个新的记录数增 1 的有序表。设整个排序有 n 个数，则 进行 n-1 趟排序，即 :先将序列中的第一个记录看成一个有序的子序列，然后第2 个记录起逐个进行插入，直接整个序列变成按关键字非递减有序列为止； 快速
6、排序 ，是通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列； 堆排序，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用 Heapify 实现的。2.概要设计2.1 主要全程变量和数据结构(1)数据结构：#include stdlib.h#include #define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,
7、rec; int a7,b7;file().(2)算法的入口及其说明#include#define s 100/ 宏定义命令typedef struct record/ 记录声明的结构体int key;/ 定义变量staticstruct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7; / 记录静态变量结构体file()/ 系统定义printf(*n);printf(*1.直接插入排序*n);printf(*2.希尔排序*n);printf(*3.起泡排序*n);printf(*4.快速排序*n);printf(*5.简单选择排序*n);printf
8、(*6.堆排序*n);printf(*7.总结*n);printf( * *0. 退出 * n);printf( * n); 以上 printf( * n);为系统主菜单输出2.2 程序模块结构程序划分为以下几个模块（即实现程序功能所需的函数）主控菜单项选择函数 :menu_select()插入排序函数 :InsertSort （）选择排序函数： StlectSort()起泡排序函数： BubbleSort()堆排序函数： heapsort （）快速排序函数： Quicksort （）希尔排序： Shell Sort（）.3.详细设计3.1 程序的主要结构如下图所示。图 3-1 函数调用关系图
9、其中 main()是主函数，它进行菜单驱动，根据选择项 10 调用相应的函数3.2 数据结构定义图 3-2 课程设计流程图.3.3 显示各排序算法排序后的的数据。图 3-3 程序工作流程图3.4 函数实现（例如直接插入排序）#include stdlib.h#include #define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file()printf( * n);printf( * *1. 直接插入排序 * n);printf( * *0. 退出
10、 * n);printf( * n); void Straight_insert_sort(r,n) /* 直接插入 */struct record r;int n; int i,j; a1=0;b1=0;.for(i=1;i=n;i+)printf(%4d,ri.key);printf(n);for(i=2;i=0) & (r0.keyrj.key) b1+;rj+1=rj-;rj+1=r0;a1=a1+2;printf(* 直接插入 *n);for(i=1;i=n;i+)printf(%4d,ri);printf(n);printf(move:%d time, compete:%d tim
11、e,a1,b1); printf(n);4.调试分析4.1 直接插入排序将一个记录插入到已排好的有序表中， 从而得到一个新的，记录数增加 1 的有序表4.2 起泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。 依此类推，知道第 N-1 个和第N个记录的关键字进行过比较为止。上述为第一趟排序。其结果使得关键字的最大被安排到最后一个记录的位置上。 然后进行第二趟起泡排序， 对前 N-1 个记录进行同样操作。一共要进行 N-1 趟起泡排序。4.3 直接选择排序每一趟从待排序的记录中选出关键字最小的，顺序放在以排好序的子文
12、件的最后，知道全部记录排序完毕。.4.4 希尔排序先取一个小于 n 的整数 d，作为第一个增量，把文件全部记录全部分成 d1 个组。所有距离为 d1 的倍数的记录放在同一个组中。先在个组中进行直接插入排序：然后，取第二个增量 d2d1 重复上述的分组和排序，直至所取的增量 dt=1 （ dtdt-1d2d1 ）,即所有记录放在同一组中进行直接插入排序为止。4.5 快速排序设置两个变量 i、 j，排序开始的时候： i=0 ， j=N-1 ； 以第一个数组元素作为关键数据，赋值给 key ，即 key=A0 ；从 j 开始向前搜索，即由后开始向前搜索（ j-），找到第一个小于 key 的值 Aj
13、，Ai 与 Aj 交换；从 i 开始向后搜索，即由前开始向后搜索（ i + ），找到第一个大于 key 的 Ai ， Ai 与 Aj 交换；重复第 3、4、5 步，直到 I=J； (3,4 步是在程序中没找到时候 j=j-1 ，i=i+1 ，直至找到为止。找到并交换的时候 i， j 指针位置不变。另外当 i=j 这过程一定正好是 i+ 或 j- 完成的最后令循环结束。 ）4.6 堆排序堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用 Heapify 实现的。 堆排序的最坏时间复杂度为 O(nlogn) 。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次
14、数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 O(1 ）。排序算法时间复杂度空间复杂度是否稳定直接插入排序O（ n2）O(1)稳定起泡排序O（ n2）O(1)稳定直接选择排序O（ n2）O(1)不稳定希尔排序O（n1.5）O(1)不稳定快速排序O(nlog 2n )O(nlog 2n)不稳定堆排序O(nlog 2nO(l)不稳定)图 4-1 时间复杂度分析.5.测试结果及运行效果（ 1） 运行程序进入程序开始菜单图 5-1 开始菜单（2）开始菜单中会出现四个选项：完全有序的情况；逆序的情况；随机排序的情况；退出。运行时选择了随机排序的情况，得到 100 个随机数的随
15、机排序，如下图。图 5-2 随机排序（3）得出随机数字后，程序列出七个选项：冒泡排序；直接插入排序；简单选择排序；快速排序；希尔排序；堆排序；退出。选择冒泡排序，对100 个随机数进行冒泡排序，得到结果如下图。.图 5-3 起泡排序（4）为了测试该程序，下面继续尝试进行了其他几种排序方式，结果如下图所示。图 5-4 直接插入排序.图 5-5 简单选择排序简单选择排序结果如上图图 5-6 快速排序快速排序结果如上图.图 5-7 希尔排序希尔排序结果如上图图 5-8 堆排序堆排序结果如上图以上图片为各种排序的结果，排序结果后显示出各种方式排序所用移动次数和比较次数，以方便比较使用。.参考文献1严蔚
16、敏 吴伟民著 .数据结构 (C 语言版 ).清华大学出版 .1999 年第一版2一华等编 .数据结构 - 使用 C 语言 .电子科技大学 .1998 年第一版3谭浩强 .C 语言程序设计（第二版） .高等教育 .2002.附录 全部代码#include stdlib.h#include #define s 100typedef struct recordint key;static struct record a1s,a2s,a3s,a4s,a5s,a6s,rec;int a7,b7;file()printf(*n);printf(*1.直接插入排序*n);printf(*2.希尔排序*n);
17、printf(*3.冒泡排序*n);printf(*4.快速排序*n);printf(*5.简单选择排序*n);printf(*6.堆排序*n);printf(*7.总结*n);printf(*0. 退出* n);printf(*n);void Straight_insert_sort(r,n) /* 直接插入 */struct record r;int n; int i,j; a1=0;b1=0; for(i=1;i=n;i+)printf(%4d,ri.key);printf(n);for(i=2;i=0) & (r0.keyrj.key). b1+;rj+1=rj-; rj+1=r0;
18、a1=a1+2;printf(* 直接插入 *n);for(i=1;i=n;i+)printf(%4d,ri);printf(n);printf(move:%d time, compete:%d time,a1,b1); printf(n);void Shell_sort(r,n) /* 希 尔 排 序 */struct record r;int n; struct record rec,temp; int i,j,t,h;a2=0;b2=0;for(i=1;i=1) h=t; for(j=h;j=0) & (ri.keyrec.key) b3+;temp=ri+h;ri+h=ri;ri=te
19、mp;.i=i-h;a2=a2+3;t=t/2;b2+;printf(* 希 尔 排 序*n);for(i=0;in;i+)printf(%4d,ri);printf(n);printf(move:%d time, compete:%d time,a3,b3); printf(n);void Bubblle_sort(r,n) /* 冒 泡 排 序 */struct record r;int n; struct record rec;int i,j,m,flag;a3=0;b3=0;for(i=1;i=n;i+)printf(%4d,ri.key);printf(n);m=n;flag=1;f
20、or(i=1;i=m-1;i+) flag=0;for(j=0;jrj+1.key) b3+;rec.key=rj.key;rj.key=rj+1.key;rj+1.key=rec.key;.a3=a3+3;flag=1;if(flag=0) break;printf(* 冒 泡 排 序*n);for(i=0;in;i+)printf(%4d,ri.key);printf(n);printf(move: %d time, compete: %d time,a3,b3); printf(n);int push(h,top,m,n)int h;int top ,m,n; h+top=m; h+to
21、p=n; return(top);int pop(h,top,m,n)int h, top,*m,*n; *m=htop-; *n=htop-; return(top);int quick(r,i,j)struct record r;int i,j;rec=ri;while(ij) while(irec.key).j-;b4+;if(ij)ri+=rj;a4+;while(ij)&(ri.key=rec.key)i+;b4+;if(ij)rj-=ri;a4+;ri=rec;a4+;return(i);void Quick_sort(r,l,h) /* 快 速 排 序 */struct reco
22、rd r;int l,h; int sss; int top,i,j,k;for(i=1;i=s;i+)printf(%4d,ri.key);printf(n);i=l;j=h;top=-1;do while(i1) top=push(ss,top,k+1,j);j=k-1;if(top0).top=pop(ss,top,&j,&i);while(top=0)|(ij);printf(* 快 速 排 序 *n);for(i=1;i=s;i+)printf(%4d,ri.key);printf(n);printf(move: %d time, compete: %d time,a4,b4);void Simple_select_sort(r,n) /* 简 单 选 择 排 序 */struct record r;int n;int i,j,m;a5=0;b5=0;for(i=1;i=n;i+)printf(%4d,ri.key);printf(n);for(i=1;i=n-1;i+) m=i; for(j=i+1;j=n;j+) if(rj.keyrm.key)m=j;b5+;if(i!=m) rec=ri; ri=rm; rm=rec;a5=a5+3;printf(* 简 单 选 择*n);for(i=1;i=s;i+)printf(%4d,ri.ke
