内部排序算法比较

1、数据结构程序设计内部排序算法比较目录摘要1.1绪论1.2系统分析1.2.1功能需求1.22数据需求1.2.3性能需求2.3总体设计2.3.1系统设计方案2.3.2功能模块设计2.4详细设计3.4.1数据结构定义3.4.2伪随机产生数据模块4.4.3简单选择排序模块5.4.4起泡排序模块6.4.5直接插入排序模块7.4.6希尔排序模块8.4.7快速排序模块9.4.8归并排序模块1.04.9条形图模块115调试与测试125.1 调试.125.2测试错误！未定义书签。6结论13结束语13参考文献14附录1用户手册15附录2源程序1.7I数据结构课程设计摘要本程序是比较几种排序算法的关键字比较次数和移

2、动次数以取得直观感受。 内部算法有冒泡排序、直接插入排序、快速排序、希尔排序、归并排序等。每种算法都有自己的比较方法和优缺点， 本程序能更直观的显示出各种排序的比 较次数、移动次数和排序时间，并能用条形图(星号表示)进行表示，以便比较 各种排序的优劣。该程序运用了数据结构中线性表的顺序存储结构和各种排序算 法来共同实现的。关键词：内部排序、条形图。1绪论随着科技的快速发展，越来越多的企业不再浪费人力财力去计算一些统计性 结果，而是应用一些简单的程序或系统来完成这些任务。随着学习数据结构课程 的深入，了解了不同排序算法的不同排序方法， 每种排序对数据的比较次数、移 动次数和排序用时都是不同的，本

3、程序实现了六种内部排序算法的比较， 并用条 形图直观的显示出各种算法的优劣。运用伪随机产生的数据，调用六种排序算法， 记录其比较次数、移动次数和排序时间，再分别用条形图(星号表示)表示出来。2系统分析2.1功能需求(1) 对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归 并排序算法进行比较。(2) 待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时 间，再汇总比较。(3) 演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便

4、比较 各种排序的优劣。2.2数据需求抽象数据类型：线性表、排序算法(1) 输入数据：需要比较的数据数目(2) 输出数据：不同算法的比较次数、移动次数、排序时间的数据以及对应的条形图。2.3性能需求在运行本程序时，只要按照正确的操作方法不会出现无法运行的情况，系统稳定性好，安全，可靠，响应速度由需比较的数字数目多少来决定。3总体设计3.1系统设计方案(1) 输入要排序的数据数目(2) 抽象数据类型定义typedef structint key;ElemType; / 关键字typedef structElemType *elem;in t le ngth;SqList;分配顺序存储结构(3) 存

5、储结构：本程序采用了线性表的顺序存储结构。(4) 算法设计：简单选择排序：运用顺序表。时间复杂度O(n2)，空间复杂度0(1)。起泡排序：时间复杂度 O(n2),空间复杂度O(1)直接插入排序：时间复杂度 O(n2)，空间复杂度O(1)希尔排序：时间复杂度O(n1.3),空间复杂度O(1)快速排序：时间复杂度 O(nlog2n),空间复杂度O(nlog2n)归并排序：时间复杂度 O(nlog2n),空间复杂度O(n)3.2功能模块设计根据分析整个程序主要划分为8个功能模块，分别执行要求中的功能。1个 产生伪随机数据模块、6个内部排序算法模块以及1个形成条形图模块。功能模 块图如图1所示图1功能

6、模块图(1) 伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生， 再用不同排序算法进行排序。(2) 简单选择排序模块：运用简单选择排序法对伪随机产生的数据进行 排序。(3) 起泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。(4) 直接插入排序模块：运用直接插入排序法对伪随机产生的数据进行 排序。(5) 希尔排序模块：运用希尔排序法对伪随机产生的数据进行排序。 快速排序：运用快速排序法对伪随机产生的数据进行排序。(7) 归并排序：运用归并排序法对伪随机产生的数据进行排序。(8) 条形图表示比较结果：统计6种排序算法的比较结果，用条形图表 示出来。4详细设计 4.1数据结构定义t

7、ypedef structint key;ElemType; / 关键字typedef structElemType *elem; in t le ngth;SqList;分配顺序存储结构4.2伪随机产生数据模块运用顺序伪随机产生数据模块可实现伪随机产生不同数目的数据以供排序,存储结构来实现的。该模块具体实现程序流程如图2所示5数据结构课程设计#数据结构课程设计开始int i;Nprintf("重新输入!n");ivn+1;i+NYL.elemi.key二ra nd();L.elemi.key>20000图2伪随机产生数据模块6数据结构课程设计4.3简单选择排序模块该

8、模块具体简单选择排序模块可实现用简单排序法对产生的数据进行排序。实现程序流程如图3所示。7数据结构课程设计#数据结构课程设计图3简单选择模块8数据结构课程设计9数据结构课程设计4.4起泡排序模块起泡排序模块可实现运用起泡排序法对数据进行排序，该模块具体实现程序流程如图4所示。图4起泡排序模块4.5直接插入排序模块直接插入排序模块可实现运用直接插入排序法对数据进行排序，该模块具体实现程序流程如图5所示。图5直接插入排序模块4.6希尔排序模块希尔排序模块可实现运用希尔排序法对数据进行排序，该模块具体实现程序流程如图6所示。图6希尔排序模块4.7快速排序模块快速排序模块可实现用快速排序法对数据进行排

9、序，该模块具体实现程序流程如图7所示。图7快速排序模块4.8归并排序模块归并排序模块可实现用归并排序法对数据进行排序，该模块具体实现程序流 程如图8所示。图8归并排序模块4.9条形图模块条形图模块可用星号显示出各种算法排序的比较结果，该模块具体实现程序流程如图9所示。5调试与测试 5.1调试调试过程主要是运行编制好的程序， 然后遇到错误后根据系统的提示，找到 相关的问题所在。本系统调试过程中遇到的主要问题、原因和解决方法如下面介 绍。 问题：用条形图表示时，不能根据数据而表示出星号的多少。解决办法：选择要表示的数据最小的一种排序作为基数，每种排序所要比较的数据可运用数学运算计算出是基数的多少倍

10、，从而输出几个星号。(2) 问题：输入数据数目为2个时程序运行错误。原因：待比较的数据为2个时，作为基数的那种排序的数据为 0,不能做分 母，所以会出现运行错误。解决方法：输入较大的数，使要用条形图表示出来的数据不为0即可。5.2测试软件测试是软件生存期中的一个重要阶段， 是软件质量保证的关键步骤从用 户的角度来看，普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件测试应该是“为了发现错误而执行程序的过程”。或者说，软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例(即输入数据及其预期的输出结果)，并利用这些测试用例去运行程序，以发现程序错误或 缺陷。过度测试

11、则会浪费许多宝贵的资源。 到测试后期，即使找到了错误，然而 付出了过高的代价。测试数据过程如下。(1)输入功能测试输入数据1： 100预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。运行结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。说明：预期和运行结果相同。输入数据2： 25000预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。运行结果：超出范围重新输入！说明：不能输入比25000大的数。(2)输出功能测试输入数据1： 200预期结果：输出各排序算法的比较次数、移动次数和排序用

12、时，随后输出数据比较所对应的条形图。运行结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。说明：预期和运行结果相同。输入数据2： 4预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。运行结果：在输出移动次数比较的条形图时出现运行错误。说明：不能输入比5小的数。6结论经过这一段时间的程序设计，该课设任务书中题目所要求的功能也都一一实现。可以伪随机产生不同的数据，六种内部排序算法对其数据进行排序， 记录比 较次数、移动次数和排序用时，并用条形图直观的表示出不同算法的优劣。 不过 本程序还可以添加细节，例如：可输出个选择排序方法

13、的菜单， 挑选不同排序方 法对数据进行比较，也可以再循环选择并用条形图表示出来。结束语为期两个星期的课程设计终于顺利完成，这段时间让我对数据结构这门课程 有更多的了解和认识，同时也从编程中所遇到的挫折和困难中吸取更多有价值的 经验。编程需要耐心和信心，要有缜密的心思来全面考虑问题， 否则编出的程序 不能完全满足题目要求或运行错误。 通过这次课设，我更深入了解了六种内部排 序算法的排序方法和时间复杂度， 从而还算顺利的完成了本次课程设计。 编程的 道路不好走，不过我会更加努力的学习，让编程不再那么困难辛苦，让以后自己 能有信心的轻松面对。参考文献1 谭浩强.C语言程序设计（第三版）.清华大学出版

14、社，20072 姜灵芝，余健.C语言课程设计案例精编清华大学出版社，20083 吴伟民，严蔚敏.数据结构清华大学出版社，2008吕映芝.编译原理.清华大学出版社，200819数据结构程序设计图9输入界面附录1用户手册9所示。点击运行，首先出现的是要输入伪随机产生数据的数目，如图20数据结构程序设计#数据结构程序设计输入数据个数然后回车，可显示出不同排序算法的比较次数、 移动次数和排 序用时。如图10所示。钗2恬祈次数十 R| CI£IOQ£feQ|1 *4852仪动决魏十的个9牺1曹动真数为Q IJiMlUilU 'O IWWJ15WW11T? IrUTFSrH&#

15、39;pIrj个数汀00務动次数为库甲时为输入你要输入的个数獰踽SJAEANtSFibb2642?40IM51 <7b9H T：DeU4We4iiiiO4£*fite图10显示比较结果界面:为为 序救时 在序:为为要 绻數时你 夷ffl入±为为異:为为要 序數时你 娄甲入數为时飪移动次数为 用时为 «, HHHHHH h你要输入的个数巩8»#数据结构程序设计#数据结构程序设计显示比较次数的条形图。如图11所示。#数据结构课程设计21数据结构课程设计图11比较次数条形图界面显示移动次数条形图。如图12所示图12移动次数条形图界面显示排序用时条形图。如

16、图13所示03 F:fiH-jQB841111lj4壬翳tQie"图13排序用时条形图界面22数据结构课程设计附录2-源程序主要模块源代码清单：#in clude<stdio.h>#in clude<stdlib.h>#i ncludevstri ng.h>#in clude<math.h>#in clude<time.h>#defi ne LIST_INIT_SIZE 30000int bj1,yd1, n,com,mov;long int A5,B5;double t0,t1,t2,t3,t4,t5,C 5;clock_t s

17、tart_t,e nd_t;typedef structint key;ElemType;typedef structElemType *elem;in t le ngth;SqList;void addlist(SqList &L)int i;a: printf("请输入你要输入的个数:");scan f("%d",&n);if(n>20000)printf("超出范围重新输入!n");goto a;L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)

18、;if(!L.elem)exit(0);L.le ngth=O;for(i=1;i <n+1;i+)b: L.elemi.key=ra nd();if(L.elemi.key>20000)goto b;+L .len gth;void SelectSort(SqList &L)start_t=clock();int i,j,k,com=0,mov=0;for(i=1;i<L .len gth;i+)k=i;for(j=i+1;j<Len gth;j+)com+;if(L.elemj.key<L.elemk.key)k=j;if(i!=k)L.elem0.k

19、ey=L.elemi.key;L.elemi.key=L.elemk.key;L.elemk.key=L.elem0.key;mov+=3;en d_t=clock();printf("比较次数为%d移动次数为t0=(double)(e nd_t-start_t)/CLK_TCK;printf("排序用时为%fn",t0);/简单选择排序%dn",com,mov);A0=com;26数据结构课程设计27数据结构课程设计B0=mov;CO=tO;void bubblesort(SqList &L)start_t=clock();int i=1,j,

20、com=0,mov=0;while(i<L .len gth)for(j=1;j<Len gth;j+)com+;if(L.elemj.key>L.elemj+1.key)L.elem0.key=L.elemj.key;L.elemj.key=L.elemj+1.key;L.elemj+1.key=L.elem0.key;mov+=3;i+;en d_t=clock();printf("比较次数为%d移动次数为t1=(double)(e nd_t-start_t)/CLK_TCK;printf("排序用时为%fn",t1);A1=com;B1=m

21、ov;C1=t1;void In sertSort(SqList &L)start_t=clock();/起泡排序%dn",com,mov);/直接插入排序28数据结构课程设计int i,j,com=0,mov=0;for(i=2;i<=Len gth;i+)if(L.elemi.key<L.elemi-1.key)L.elem0.key=L.elemi.key;mov+;j=i-1;com+;while(L.elem0.key<L.elemj.key)L.elemj+1.key=L.elemj.key;j-;mov+;com+;L.elemj+1.key=

22、L.elem0.key;mov+;en d_t=clock();prin tf("比较次数为d移动次数为dn",com,mov);t2=(double)(e nd_t-start_t)/CLK_TCK;printf("排序用时为%fn",t2);A2=com;B2=mov;C2=t2;void xier(SqList &L)希尔排序start_t=clock();int i,d=L.le ngth/2,j,w=0,k,com=0,mov=0;while(w<d)w=1;for(i=w;i<L.le ngth;i=i+d)k=i;for

23、(j=i+d;j<L.le ngth;j=j+d)if(L.elemi.key>L.elemj.key)k=j;com+;if(i!=k)L.elemO.key=L.elemi.key;L.elemi.key=L.elemk.key;L.elemk.key=L.elemO.key;mov+=3;w+;d=d/2;w=1;en d_t=clock();%dn",com,mov);printf("比较次数为%d移动次数为t3=(double)(e nd_t-start_t)/CLK_TCK;printf("排序用时为%fn",t3);A3=com

24、;B3=mov;C3=t3;void BeforeSort()yd1=O,bj 仁0;void display© nt m,i nt n)%dn",m, n);/快速排序printf("比较次数为%d移动次数为int Partiti on( SqList L,i nt low,i nt high)int pivotkey;L.elem0=L.elemlow;yd1+;pivotkey=L.elemlow.key;while (lowvhigh)yd1+;while(low<high&&L.elemhigh.key>=pivotkey)-

25、high;L.elemlow=L.elemhigh;bj1+;yd1+;while (low<high&&L.elemlow.key<=pivotkey)+low;L.elemhigh=L.elemlow;bj1+;yd1+;L.elemlow=L.elem0;yd1+;return low;void QSort(SqList & L,i nt low,i nt high)int pivotloc;if(lowvhigh)pivotloc=Partitio n( L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivo

26、tloc+1,high);void QuickSort(SqList &L)start_t=clock();BeforeSort();QSort(L,1, L.le ngth);display(bj1,yd1);en d_t=clock();t4=(double)(e nd_t-start_t)/CLK_TCK;printf("排序用时为%fn",t4);A4=bj1;B4=yd1;C4=t4;/归并排序void Merge(ElemType R,ElemType R1,int low,int m,int high)int i=low, j=m+1, k=low;w

27、hile(i<=m&&j<=high)if(Ri.keyv=Rj.key)bj1+;R1k=Ri;yd1+;i+；k+;elsebj1+;R1k=Rj;yd1+;j+;k+;while(i<=m)R1k=Ri;yd1+;i+;k+;while(j<=high)R1k=Rj;yd1+;j+;k+;void MergePass(ElemType R,ElemType R1,int length, int n)int i=0,j;while(i+2*length-1<n)Merge(R,R1,i,i+le ngth-1,i+2*le ngth-1);i=

28、i+2*le ngth;if(i+le ngth-1< n-1)Merge(R,R1,i,i+le ngth-1, n-1);elsefor(j=i;j< n;j+)R1j=Rj；void MSort(ElemType R,ElemType R1,int n)in t le ngth=1;while (le ngth <n)MergePass(R,R1,le ngth, n);len gth=2*le ngth;MergePass(R1,R,le ngth, n);len gth=2*le ngth;void MergeSort(SqList &L)start_t=c

29、lock();BeforeSort();MSort(L.ele m, L.ele m,L .le ngth);display(bj1,yd1);en d_t=clock();t5=(double)(e nd_t-start_t)/CLK_TCK;printf("排序用时为%fn",t5);A5=bj1;B 5=yd1;C5=t5;void prin tf(SqList &L)long int d6;int i,n;n");prin tf("n 比较次数prin tf("n=n");for(i=0;i<5;i+)di= s

30、qrt (Ai/A5);prin tf("n归并排序：*");prin tf("n=n");prin tf(" 选择排序：");for(n=0,i=0;n<=di; n+)prin tf("*");prin tf("n=n");printf("冒泡排序：");for(n=0,i=1; n<=di; n+)prin tf("*");prin tf("n=n"); printf("直插排序：");for(n=

31、0,i=2 ;n<=di; n+)prin tf("*");prin tf("n=n");prin tf("希尔排序：");for(n=0,i=3 ;n<=di; n+)prin tf("*");prin tf("n=n");prin tf(" 快排排序： ");for(n=0,i=4 ;n<=di; n+)prin tf("*");prin tf("n=n");n");prin tf("n 移动次

32、数prin tf("n=n"); double e6;for(i=0;i<6;i+)ei= sqrt (Bi/B3);prin tf("n希尔排序：*");prin tf("n=n");prin tf(" 选择排序： ");for(n=0,i=0;n<=ei; n+)prin tf("*");prin tf("n=n");prin tf("冒泡排序： ");for(n=0,i=1; n<=ei; n+)prin tf("*");prin tf("n=n"); printf("直插排序： ");for(n=0,i=2 ;n<=ei; n+)prin tf("*");prin tf("n=n");prin tf("快排排序：");for(n=0,i=4 ;n<=ei; n+)prin tf("*");prin tf("n=n");prin tf("归并排序：");for(n=0,i=5 ;n&l