《数据结构c语言设计,比较各种排序方法的效率.doc》由会员分享，可在线阅读，更多相关《数据结构c语言设计,比较各种排序方法的效率.doc（32页珍藏版）》请在三一文库上搜索。
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;
11、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; /将Rj与Rj+1交换Rj+1=R0;b1+=3; /简单选择排序void Select_Sort(datatype R,int n)/简单选择排序int i,j,k; for(i=1;in;i+)k=i; for(j=i+1;j=n;j+)
12、a2+; if(Rj.keyRk.key) /选择第i小的记录k=j;if(i!=k)R0=Rk;Rk=Ri; /将Rk与Ri交换Ri=R0;b2+=3; /快速排序int Partition(datatype R,int low,int high)int pivotkey; R0=Rlow;b3+; pivotkey=Rlow.key; /枢轴记录关键字while(lowhigh)while(low=pivotkey)a3+; -high; if(lowhigh)Rlow=Rhigh; /将比枢轴记录小的记录移到低端a3+;b3+; while(lowhigh&Rlow.keyR0.key)
13、a3+; +low; if(lowhigh)Rhigh=Rlow; /将比枢轴记录大的记录移到高端a3+;b3+; Rlow=R0;b3+; return low; /返回枢轴位置/Partitionvoid QSort(datatype R,int low,int high)/快速排序int i;if(lowhigh)i=Partition(R,low,high); /将Rlow.high一分为二QSort(R,low,i-1); /对低子表递归排序，i是枢轴位置QSort(R,i+1,high); /对高子表递归排序/QSort/堆排序void HeapAdjust(datatype R,
14、int s,int m)datatype rc;int j;rc=Rs;for(j=2*s;j=m;j*=2) /沿key较大的孩子节点向下筛选if(jm & Rj.keyRj+1.key) a4+;+j; /j为key较大记录的下标if(jRj.key) break;Rs=Rj; b4+; s=j;Rs=rc; /插入/HeapAdjustvoid HeapSort(datatype R,int n)/堆排序int i; for(i=n/2;i0;-i)HeapAdjust(R,i,n); /将R1.n建成大顶堆for(i=n;i1;-i)R0=R1;R1=Ri; /将R1与Ri交换Ri=R
15、0;b4+=3; HeapAdjust(R,1,i-1); /将R1.i-1重新调整为大顶堆 /HeapSort/输出函数void Pri(datatype R,int n)/输出函数 int i;for(i=1;i=n;i+) printf(%d ,Ri.key); printf(n);/随机生成函数void rand_select(int n)/随机生成函数int i;LARGE_INTEGER m_liPerfFreq=0;LARGE_INTEGER m_liPerfStart=0; LARGE_INTEGER liPerfNow=0;datatype R1MAXSIZE,R2MAXSI
16、ZE,R3MAXSIZE,R4MAXSIZE; for (i=1; i=n; i+) printf(%d , Ri.key=rand()%n); printf(n); for(i=1;i=n;i+)R1i.key=Ri.key; for(i=1;i=n;i+)R2i.key=Ri.key; for(i=1;i=n;i+) R3i.key=Ri.key; for(i=1;i=n;i+) R4i.key=Ri.key; QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始In
17、sert_Sort(R, n); /直接插入排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart; c0+=Ttime; printf(插入排序后数据的顺序:n);Pri(R,n); QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始Bubble_Sort(R1, n); /
18、冒泡排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart; c1+=Ttime; printf(冒泡排序后数据的顺序:n); Pri(R1,n); QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始Select_Sort(R2, n); /简单选择排序QueryPerform
19、anceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart; c2+=Ttime; printf(简单排序数据的顺序:n); Pri(R2,n);QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始QSort(R3,1,n); /快速排序QueryPerformanceCounter(&liPerfNow);
20、/计时结束 Ttime=(liPerfNow.QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart; c3+=Ttime; printf(快速排序后数据的顺序:n); Pri(R3,n); QueryPerformanceFrequency(&m_liPerfFreq); QueryPerformanceCounter(&m_liPerfStart); /计时开始HeapSort(R4,n); /堆排序QueryPerformanceCounter(&liPerfNow); /计时结束 Ttime=(liPerfNow.
21、QuadPart)-(m_liPerfStart.QuadPart)*1000.0/m_liPerfFreq.QuadPart; c4+=Ttime; printf(堆排序后数据的顺序:n); Pri(R4,n); /主函数void main() int i,n,t; srand(unsigned)time(NULL);/使用系统定时/计数器的值 /做为随机种子每次运行，显示的随机数会是伪随机数,结果都不同 printf(n);printf(n);printf(n);printf( *-*n); m:printf( |请输入随机生成数据的个数|n); printf( *-*n); scanf(
22、%d,&n); if(n100) printf(取数个数不能小于100,请重新输入!n); goto m;printf(n);printf(n);printf( *-*n);printf( |请输入随机生成的次数|n); printf( *-*n);scanf(%d,&t);printf(n);for(i=0;it;i+)printf(电脑第%d次随机生成数据为:n,i+1);rand_select(n);printf(统计第%d次随机数据的比较次数和交换次数为n,i+1);printf(*-*n);printf(*排序方式 比较次数 交换次数 耗时n);printf(n);printf(*直
23、接 %-10dt%-10dt%-12fn,a0,b0,c0);printf(n);printf(*冒泡 %-10dt%-10dt%-12fn,a1,b1,c1);printf(n);printf(*简单选择 %-10dt%-10dt%-12fn,a2,b2,c2);printf(n);printf(*快速排序 %-10dt%-10dt%-12fn,a3,b3,c3);printf(n);printf(*堆排序 %-10dt%-10dt%-12fn,a4,b4,c4);printf(*-*n);printf(n); printf(求得平均比较次数和平均移动次数为 n);printf(*-*n);
24、printf(*排序方式 平均比较次数 平均交换次数 平均耗时n);printf(n);printf(*直接 %-10dt%-10dt%-12fn,a0/t,b0/t,c0/t);printf(n);printf(*冒泡 %-10dt%-10dt%-12fn,a1/t,b1/t,c1/t);printf(n);printf(*简单选择 %-10dt%-10dt%-12fn,a2/t,b2/t,c2/t);printf(n);printf(*快速排序 %-10dt%-10dt%-12fn,a3/t,b3/t,c3/t);printf(n);printf(*堆排序 %-10dt%-10dt%-12
25、fn,a4/t,b4/t,c4/t);printf(*-*n);4程序运行效果4.1登陆界面（100个数据随机生成5次）4.2各种排序结果显示画面（100个数据随机生成5次）第1次生成画面：（100个数据随机生成5次）第5次生成画面：4.3总的和平均的比较次数和交换次数显示（100个数据随机生成5次）4.4总的和平均的比较次数和交换次数显示（1000个数据随机生成100次）五使用说明本设计比较各种排序算法的效率能在家用或公用计算机上的VC软件上使用.六设计心得（1）课程设计中遇到的主要问题和解决方法：上学期刚学完数据结构这本书，毕竟都很少实践操作，做这个比较排序算法的效率都有些挑战，在这个课程
26、设计中，主要是对于一些基本的知识，熟悉程度不够，特别是对于比较次数和交换次数的统计，刚开始是跟理论值相差甚大，然后自己看了好几遍的书和上网看了一些例题，根据输入两个随机生成数据，比较次数为1的依据才把问题解决。在编译时有时会出现较多的出错提示，这时要理解提示信息的含义，并据此改正错误。当编译提示的出错信息不止一条时，只须先注重其中第一条，每次改完一个错误后先编译一次，因为从第二个错误开始的若干错误很可能是随带错误，只要更正了第一个错误可能就没有错误出现了，而且我们可以用printf语句来测试某条有返回值的语句是否执行。（2）我的创新和得意之处： 这个比较排序算法的效率，使用系统定时/计数器的值
27、srand(unsigned)time(NULL) ;做为随机种子每次运行，显示的随机数会是伪随机数,结果都不同，是可以随意输入随机生成数据的个数，程序执行时可以输入大量数据，有利于精确求取比较次数和交换次数。（3）设计中存在的不足及改进的设想：设计过程中，程序不够简练，另外计时语句显得比较冗长，因为是高精度时间，因此统计比较次数和交换次数的工作应该是短期内能完成的工作，时间太长，误差会特别大，因为线程有占用时间片的因素存在。不过总的来说这个设计功能还是比较完善，它很好记录了排序过程中的时间差。（4）本次课程设计的感想和心得体会： 此次课程设计，自拿到题目到完成整个编程，从理论到实践，在短短的
28、天数，发现很多以前没有注意到的知识点，学到很多东西，巩固了以前所学过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，才能提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，很多问题自己都可以解决，有时利用printf语句来测试某条语句是否执行，或用/* */暂且分隔出某部分来执行其他语句，能够很快的找到问题所在。在设计的过程中发现了自己的不足之处，对一些前面学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，我加深所学过的知识的理解与运用。在学习的过程中，独立完成，很好的提升了自己的能力，也锻炼了自己的耐力。 27