《数据结构c语言设计,比较各种排序方法的效率》由会员分享，可在线阅读，更多相关《数据结构c语言设计,比较各种排序方法的效率（31页珍藏版）》请在金锄头文库上搜索。
1、课程设计说明书设计名称： 程序设计语言强化课程设计 题 目： 比较各种排序方法的效率 学生姓名： 梁汉荣 专 业： 网络工程 班 级： 10网络工程 2 学 号： 2010394236 指导教师： 顾艳春 日 期： 2012 年 3 月 8日课程设计任务书一、 设计题目比较各种排序方法的效率二、 主要内容 选择四种以上的排序方法，采用随机生成的数据，登记并比较各个排序方法的比较次数和交换次数，验证各个排序方法效率的理论分析的结果。三、 具体要求围绕课程设计的目的和意义，基本要求如下：每次随机生成的数据不小于100个采用顺序存储结构，登记多次结果经过大量的统计计算，给出各种排序方法的平均效率的比
2、较。把统计结果与理论分析结论进行对照。四、 进度安排1、资料查找、系统分析，概要设计；时间安排2天2、系统详细设计、功能设计；时间安排2天3、算法实现、编程调试；时间安排5-7天4、资料整理、课程设计说明书编写。时间安排1天五、 完成后应上交的材料1、课程设计说明书（所使用的数据结构说明、程序流程图、功能模块图、核心算法等）2、相关源程序文件六、 总评成绩指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日目 录一、设计任务的主要算法分析11.1主要算法具体分析 2二、程序的流程图3各种排序算法的N-S图31.总流程图模块 32.直接插入排序模块43.冒泡排序模块 54.简单选择模块
3、55.快速排序模块 66.堆排序模块 6三、各个模块的源代码 731各种排序算法71.直接插入排序函数72.冒泡排序函数 8 3.简单选择排序函数94.快速排序函数 105.堆排序函数 116. 输出函数 137.随机生成函数 138.主函数 16四、程序运行效果图 204.1登陆画面 204.2 各种排序结果显示画面（100个数据随机生成5次）214.3总的、平均的比较次数和交换次数显示画面（100个数据随机 生成5次）234.4总的、平均的比较次数和交换次数显示画面（1000个数据随机生成100次）24五、使用说明24六、设计心得 246.1 课程设计中遇到的主要问题和解决方法 246.2
4、 本程序的创新和得意之处 25 6.3 设计中存在的不足及改进的设想 256.4 本次课程设计的感想和心得体会25佛山科学技术学院课程设计用纸一. 算法分析 主程序直接插入冒泡排序简单选择快速排序堆排序随机生成直接插入排序：将记录插入到已排好序的有序表中，得到一个新的，记录数增加的有序表。冒泡排序：是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。 每趟冒泡都将待排序列中的最大（小）关键字交换到最后位置，直到全部元素有序为止。简单选择排序：令i从1至n-1，进行n-1趟选择操作。快速排序：通过一趟排序将待排记录
5、分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。堆排序：使记录序列按关键字非递减有序排列，则在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。随机生成函数：用srand(unsigned)time(NULL)随机生成数据并使用不同排序方法排序。定义结构体数组typedef int keytype; /定义关键字类型为整型typedef structkeytype key;datatype;
6、 /记录类型datatype RMAXSIZE; /定义结构体数组1.1主要算法具体分析：这个排序算法设计个以静态结构体应用为基础加上C的基础语法一起的一个综合系统程序。1主程序是goto语句和for循环的应用2直接插入函数是一个将记录插入到已排好序的静态数组的应用3冒泡排序函数是一个将数据不断交换排序的应用4简单选择函数是一个从n-i+1个记录中选出最小关键字并和第i个记录交换的应用5快速排序函数是一个将每趟记录分成独立两部分并比较交换的应用6堆排序函数是一个将记录建成堆并交换的排序的应用7随机生成函数是用srand(unsigned)time(NULL)随机生成数据的应用8输出函数是一个对
7、排好序的组数输出的应用二程序的流程图 2.1总流程图输入随机生成数据的个数n100TFgoto m;输入随机生成的次数for(i=0;it;i+)rand_select(n);统计第%d次随机数据的比较次数和交换次数平均比较次数和平均移动次数说明：利用判断语句判断，若n100则执行goto语句；利用for循环语句执行随机生成函数并输出结果。2. 2直接插入排序函数for(i=2;i=n;+i)a0+Tif(Ri.keyRi-1.key)FR0=Ri;Ri=Ri-1;b0+=2;for(j=i-2;R0.keyRj.key;-j)Rj+1=Rj; b0+;a0+;if(j!=0)TFa0+;b0
8、+; Rj+1=R0; b0+;说明：利用外循环for语句，内嵌判断语句if(Ri.keyRi-1.key)和内循环for语句。2. 3冒泡排序函数for(i=1;i=n-1;i+)for(j=1;jRj+1.key)Fa1+;Rj Rj+1b1+=3;说明：利用内外循环for语句，并判断if(Rj.keyRj+1.key)进行排序。2.4简单选择函数for(i=1;in;i+)for(j=i+1;j=n;j+)Tif(Rj.keyRk.key)Fa2+;RkRi ;b2+=3;k=i;k=j;if(i!=k)TF说明：for外循环，内嵌for循环和判断语句来进行选择交换排序。2.5快速排序函
9、数Tif(lowhigh)Fint i;i=Partition(R,low,high);递归调用QSort(R,low,i-1);递归调用QSort(R,i+1,high);说明：判断if(low0;-i)for(i=n;i1;-i)R1Ri b4+=3;HeapAdjust(R,i,n);HeapAdjust(R,1,i-1);int i；说明：执行第一个for循环，不断调用HeapAdjust(R,i,n)函数；执行第二个for循环，不断交换数据和HeapAdjust(R,1,i-1)函数。三原代码程序3.1各种排序算法#include#include#include#include #d
10、efine MAXSIZE 50000typedef int keytype; /定义关键字类型为整型typedef structkeytype key;datatype; /记录类型datatype RMAXSIZE; /定义结构体数组int a5=0,b5=0; /分别定义比较次数和交换次数double c5,Ttime; /直接插入排序void Insert_Sort(datatype R,int n)/直接插入排序 int i,j; for(i=2;i=n;+i) a0+; if(Ri.keyRi-1.key)R0=Ri; /复制为哨兵Ri=Ri-1;b0+=2; for(j=i-2;R0.keyRj.key;-j)Rj+1=Rj; /记录后移 b0+; a0+;if(j!=0) a0+;Rj+1=R0; /插入到正确位置b0+; /冒泡排序void Bubble_Sort(datatype R,int n)/冒泡排序int i,j; for(i=1;i=n-1;i+)for(j=1;jRj+1.key) R0=Rj;Rj=Rj+1; /
