几种常见的排序算法的实现与性能分析数据结构课程设计报告

1、 目录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分34 详细设计341数据类型的定义342主要模块的算法描述45 测试分析246 课程设计总结30参考文献31附录（源程序清单）321 问题描述设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果。2 需求分析当今社会，我们知道是信息化时代，那么排序算法对于计算机信息处理很重要，一

2、个好的排序不仅可以使信息查找的效率提高，而且还直接影响着计算机的工作效率。目前，最常见的排序算法有直接排序法、希尔排序法、冒泡排序法、选择排序法、快速排序法、堆排序等算法。这些排序算法各有自己的优缺点，不同的排序算法适应不同的情况。就算法的整体性能而言,目前很难提出一种适应所有的排序场合的最好的排序算法，每种算法都有自己不同的适用场合。使用插入排序法，交换排序法，选择排序法设计与实现算法程序完成线性表的排序号。通过测试分析说明各排序算法的优缺点。通过实验结果分析，总结直接排序法、希尔排序法、冒泡排序法、选择排序法、快速排序法、堆排序等算法六类算法的特点。我们需要首先，用数组S来存放系统随机产生

3、的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。然后，利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。最后，在主函数中调用用户自定义函数，输出比较结果。3 概要设计31抽象数据类型定义排序数据类型定义：ADT paixu数据对象：D=aij|aij属于1，2，3,i,j>0数据关系：R=<ai-1,ai>|ai-1,aiD，i=2,.,n基本操作：Insertsort();初始条件：数组已经存在。

4、基本思想：每一步将一个待排序的序列的记录，按其主关键的大小插入到前面已经排序的文件中适当的位置，知道全部插完为止。Shellsort();初始条件：数组已经存在。基本思想：先取定一个正整数d1<n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组内进行插入排序，然后取d2<d1重复上述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。Bubblesort();初始条件：数组已经存在。基本思想：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。QuickSort(int low,int high)；初始条件：数组已经存

5、在。基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的安置在一部分，所有键值比它大的安置在另一部分，并把该记录排在两部分的中间，也就是该记录的最终位置。这个过程称为一趟快速排序。然后分别对所划分的两部分重复上述过程，一直重复到每部分内只有一个记录为止排序完成。Selectsort();初始条件：数组已经存在。基本思想：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完。对待排序的文件进行n-1趟扫描，第i趟扫描选出剩下的n-i+1个记录，并与第i个记录交换。 Heap

6、();初始条件：数组已经存在。基本思想：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列（称为初建堆），这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进行，知道把全部键值排好序为止。ADT 排序32模块划分本程序包括两个模块：（1）主程序模块void main()初始化；随机数的产生；调用子函数；（2）子函数模块：实现直接插入排序的抽象数据类型。 实现希尔排序的抽象数据类型。 实现冒泡排序的抽象数据类型。 实现快速排序的抽象数据类型。 实现选择排序的抽象数据类型。 实现堆排序的抽象数据类型。最后输出相应算法的比较次数(至少有五种不同的数据)和

7、移动次数（关键字的交换记为三次移动）。从而直观的判断各内部排序算法性能的优劣性。4 详细设计41数据类型的定义(1)直接插入排序类型：void Insertsort();(2)希尔排序类型：void Shellsort();(3)冒泡排序类型：void Bubblesort();(4)快速排序类型：void QuickSort(int low,int high);(5)选择排序类型：void Selectsort();(6)堆排序类型：void Heap();42主要模块的算法描述（1）系统的总体结构内部排序算法性能分析堆排序快速排序选择排序冒泡排序希尔排序直接插入排序输出各种排序的排序结果和

8、排序的比较次数和移动次数 图4.20总体结构图 （2）运行环境与开发环境 六种排序结构的性能分析的运行环境规定为： 硬件配置：单机系统。 软件配置：windows操作系统。 开发平台：该程序借助C语言编程实现，事例采用Vinual C+作为编程开发工具。 （3）下面是主程序的结构图和几个主要模块的流程图和相应的程序代码开始 循环产生一组随机数将随机数保存在数组中堆排序选择排序快速排序起泡排序希尔排序插入排序记录关键字的比较次数和移动次数输出关键字的比较次数和移动次数结束 4.21主程序结构图 排序是一种重要的数据结构，在我们的现实生活中有许多地方要用到排序，比如：学生的成绩，当学生人数比较少是

9、我们可以人工的进行排序，但是当学生数量达到一定程度，我们进行人工排序会花费大量的时间。那这时我们所编写的排序程序就派上大的用场了，我们所编写的程序有六种基本的排序方法，以下就是我们一个整体排序的代码，能体现我们六种排序的一个基本的结构，通过这里我们可以选择相应的序号进行相应的排序，以下就是整体排序的代码：#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define L 100#define FALSE 0#define TRUE 1/*typedef

10、structint key;char otherinfo;RecType;*/typedef RecType SeqlistL+1;int s100,R100;int num;int times=0,changes=0;/Seqlist R;void Insertsort();void Bubblesort();void QuickSort(int low,int high);void Shellsort();void Selectsort();void Heap();int Partition();void main()/Seqlist S;int i,k;char ch1,ch2,q;pr

11、intf("产生100个随机数：n"); srand(unsigned)time(NULL); for(i=1;i<=L;i+) si=rand()%100; for(i=1;i<=L;i+) printf("%4d",si); printf("nt排序数据已经输入完毕！"); for(i=1;i<=L;i+)Ri=si; ch1='y'while (ch1='y'|ch1='Y')printf("nnnnnttt排 序 性 能 分 析n"); pr

12、intf("tt*n"); printf("tt* 1-直接插入排序 -*n"); printf("tt* 2-希 尔 排 序 -*n"); printf("tt* 3-冒 泡 排 序 -*n"); printf("tt* 4-快 速 排 序-*n"); printf("tt* 5-选 择 排 序 -*n"); printf("tt* 6-堆 排 序-*n"); printf("tt* 0-返 回-*n"); printf("

13、tt*n"); printf("tt请选择菜单号（0-6）:");scanf("%c",&ch2);getchar();for(i=1;i<=L;i+)Ri=si;switch(ch2)case '1':Insertsort();break;case '2':Shellsort();break;case '3':Bubblesort();break; case '4': printf("ntt尚未排序的数据为（回车继续）："); for(k=1;k

14、<=L;k+) printf("%5d",Rk); getchar();printf("n"); num=0;QuickSort(1,L); break;case '5':Selectsort();break; case '6':Heap();break;case '0':ch1='n'break;default:printf("tt输入错误！请重新输入！ntt");if(ch2!='0')if(ch2='2'|ch2='3&

15、#39;|ch2='4'|ch2='5'|ch2='6'|ch2='7'|ch2='8')printf("nt排序演示输出完毕！n"); printf("nt请按回车键返回主菜单.");q=getchar();if (q!='xA') getchar();ch1='n'结束printf(“%5d,”Rk);输入要排序的一组元素i=2getchar();Maltiplexprintf(“/n/n”);i+Maltiplexi<=Lk+开始k

16、<=Lk=1int i,j,k,m=0NYNYY4.22直接排序关键字比较次数和移动次数的流程图此函数void Insertsort()的程序代码如下：void Insertsort()/直接插入排序int i,j,k,m=0; printf("ntt尚未排序的数据为（回车继续）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=2;i<=L;i+)if(Ri<Ri-1) R0=Ri;j=i-1;while(R0<Rj) tim

17、es+; changes+;Rj+1=Rj;j-;Rj+1=R0; changes+;m+; times+;printf("nn"); printf("t最终排序结果为：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt直接插入排序的比较次数为%d",times); printf("nt直接插入排序的移动次数为%d",changes); times=0; changes=0;开始输入要排序的一组元素初始

18、化变量i,j,gap=L/2,m=0m小于gapi小于元素总个数j=i+gapj小于元素总个数第i个元素大于第j个元素交换第i个元素第j个元素gap为原来的一半输出关键字的比较次数和移动次数结束4.23希尔排序关键字比较次数和移动次数此函数 void Shellsort() 的程序代码如下：void Shellsort() /希尔排序int i,j,gap,x,m=0,k; printf("nt尚未排序的数据为（回车继续）："); for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n&q

19、uot;);gap=L/2;while (gap>0)for(i=gap+1;i<=L;i+) j=i-gap;while(j>0) times+;if (Rj>Rj+gap)x=Rj;Rj=Rj+gap;Rj+gap=x;j=j-gap; changes+; elsej=0;gap=gap/2;m+;printf("nn"); printf("t最终排序结果为：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("

20、nt希尔排序的比较次数为%d",times); printf("nt希尔排序的移动次数为%d",changes); times=0; changes=0;开始输入要排序的一组元素i=1,j=1定义临时中间变量k，并赋初值i<元素总个数 N i<i+1j<元素总个数 N Y j=j+1第j个元素>第j+1个元素 Y N利用k交换第j个元素和第j+1个元素 Y输出比较次数和移动次数结束 4.24冒泡排序关键字比较次数和移动次数的流程图此函数void Bubblesort() 的程序代码如下：void Bubblesort()/冒泡排序int i

21、,j,k; int exchange; printf("ntt尚未排序的数据为（回车继续）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=1;i<=L;i+)exchange=FALSE;for(j=L;j>=i+1;j-) times+; if(Rj<Rj-1) R0=Rj; Rj=Rj-1; Rj-1=R0; exchange=TRUE; changes+=3;if(exchange); printf("nn&quo

22、t;); printf("t最终排序结果为：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt冒泡排序的比较次数为%d",times); printf("nt冒泡排序的移动次数为%d",changes); times=0; changes=0;开始输入要排序的一组元素初始化变量priot，low，highLow小于highYHigh减1Low+第low个元素与第high个元素交换第high个元素大于priot第high个元

23、素与第low个元素交换第low个元素小于priot结束输出关键字的比较次数和移动次数YY4.25快速排序关键字比较次数和移动次数的流程图此函数int Partition(int i,int j) 的程序代码如下：int Partition(int i,int j) /快速排序int pirot=Ri;while(i<j)while(i<j&&Rj>=pirot)j-; times+;if(i<j)Ri+=Rj; changes+;while(i<j&&Ri<=pirot)i+; times+;if(i<j)Rj-=Ri;

24、 changes+;Ri=pirot;return i;void QuickSort(int low,int high)int pirotpos,k,i;if (low<high)pirotpos=Partition(low,high);num+;QuickSort(low,pirotpos-1); QuickSort(pirotpos+1,high);printf("nn"); printf("t最终排序结果为：n");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n&quo

25、t;);printf("nt快速排序的比较次数为%d",times);printf("nt快速排序的移动次数为%d",changes);times=0;changes=0;开始输入要排序的一组元素i=1，j=1定义临时中间变量h，并赋初值i<元数总个数 N做第i趟排序 Yi=i+1在无序区Ri-n中选h最小记录Rhh记下目前找到的最小关键字所在的位置交换Ri和Rh输出比较次数和移动次数结束 4.26选择排序关键字比较次数和移动次数的流程图此函数void Selectsort() 的程序代码如下：void Selectsort() /选择排序int

26、i,j,k,h; printf("ntt尚未排序的数据为（回车继续）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=1;i<=L;i+) h=i;for(j=i+1;j<=L;j+)times+; if (Rj<Rh)h=j;if(h!=j)R0=Rh;Rh=Ri;Ri=R0; changes+=3; printf("nn"); printf("t最终排序结果为：");for(i=1;i&l

27、t;=L;i+)printf("%5d",Ri);printf("n"); printf("nt选择排序的比较次数为%d",times); printf("nt选择排序的比较次数为%d",changes); times=0; changes=0;开始输入要排序的一组元素定义临时中间变量k，并赋初值将二叉树转换成堆i=总元素个数-1i<=1 N将堆的根植和最后一个值交换 Yi-,k+输出比较次数和移动次数结束4.27堆排序关键字比较次数和移动次数的流程图此函数void CreateHeap(int root,i

28、nt index)的程序代码如下：void CreateHeap(int root,int index)/建堆int j,temp,finish;j=2*root;temp=Rroot;finish=0;while (j<=index&&finish=0)if (j<index)if (Rj<Rj+1) j+; times+; if(temp>=Rj) finish=1; /堆建立完成 times+; elseRj/2=Rj;/父结点=当前结点j=j*2; changes+;Rj/2=temp; /父结点=root值void HeapSort()int

29、i,j,temp,k;for(i=(L/2);i>=1;i-)/将二叉树转换成堆CreateHeap(i,L);/建堆 for(i=L-1,k=1;i>=1;i-,k+)temp=Ri+1;/堆（heap）的root值和最后一个值交换Ri+1=R1;R1=temp; changes+=3;CreateHeap(1,i);void Heap() int k; printf("nt尚未排序的数据为（回车继续）："); for(k=1;k<=L;k+)printf("%5d",Rk);printf("nt");getcha

30、r();HeapSort();printf("nn"); printf("t最终排序结果为：");for(k=1;k<=L;k+)printf("%5d",Rk);printf("n"); printf("nt堆排序的比较次数为%d",times); printf("nt堆排序的移动次数为%d",changes);times=0;changes=0;5 测试分析以下是进行了99趟排序后，得到了最终的排序结果，并且也知道了直接插入排序的比较次数和移动次数 下面是希尔排序的

31、性能比较 以下是冒泡排序的性能比较 以下是快速排序的性能比较 以下是选择排序的性能比较 以下是堆排序的性能比较 以下是返回结果以上就是对六种排序算法的一种演示，经过观察和分析我们可以比较六种排序的性能。6 课程设计总结通过本次课程设计，我对直接插入排序，希尔排序，选择排序等六种排序的概念有了一个新的认识。我觉得学习数据结构不仅仅只是停留在书本上的知识，了解它们的排序结果。我们应该不断的探索，创新，发现解决问题的新的方法，通过对这六种排序方法做比较，使得我们在处理一些问题的时候比较简便，也让我了解到程序的神奇之处。我们这组的题目是各种排序性能的比较，这就要求我首先必须掌握各种排序的原理，并且还要

32、把各个排序结合起来综合考虑。我在实现排序功能是没有遇到太大的问题，但在进行快速排序的时候，程序出了点小问题，曾经多次尝试修改，但始终没有运现出来。通过这次课程设计，也使我对数据结构有了更进一步的认识和了解，要通过不断的上机操作才能更好地学习它，我也发现我的许多不足之处，对C+语言的一些知识还不是很熟练，不能熟练掌握各种常用函数的功能，对函数调用的正确使用不够熟悉，对C+中经常出现的错误也不熟悉。通过这次课程设计，我更加体会到了实践的重要性。此外，此次课程设计感谢我的方爱菊同学，在我们两个的一起努力下，圆满的完成了此次课程设计。同时也十分感谢黄同成老师对我们的悉心指导，使得我们一些程序上的问题的

33、到了解决。我们一定会加强对数据结构的学习，使得自己达到一个较高的水平。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003 附录（源程序清单）#include <stdio.h>#include <stdlib.h>#include <math.h>#include <time.h>#define L 10

34、0#define FALSE 0#define TRUE 1/*typedef structint key;char otherinfo;RecType;*/typedef RecType SeqlistL+1;int s100,R100;int num;int times=0,changes=0;/Seqlist R;void Insertsort();void Bubblesort();void QuickSort(int low,int high);void Shellsort();void Selectsort();void Heap();int Partition();void ma

35、in()/Seqlist S;int i,k;char ch1,ch2,q;printf("产生100个随机数：n"); srand(unsigned)time(NULL); for(i=1;i<=L;i+) si=rand()%100; for(i=1;i<=L;i+) printf("%4d",si); printf("nt排序数据已经输入完毕！"); for(i=1;i<=L;i+)Ri=si; ch1='y'while (ch1='y'|ch1='Y')prin

36、tf("nnnnnttt排 序 性 能 分 析n"); printf("tt*n"); printf("tt* 1-直接插入排序 -*n"); printf("tt* 2-希 尔 排 序 -*n"); printf("tt* 3-冒 泡 排 序 -*n"); printf("tt* 4-快 速 排 序-*n"); printf("tt* 5-选 择 排 序 -*n"); printf("tt* 6-堆 排 序-*n"); printf(

37、"tt* 0-返 回-*n"); printf("tt*n"); printf("tt请选择菜单号（0-6）:");scanf("%c",&ch2);getchar();for(i=1;i<=L;i+)Ri=si;switch(ch2)case '1':Insertsort();break;case '2':Shellsort();break;case '3':Bubblesort();break; case '4': printf(&q

38、uot;ntt尚未排序的数据为（回车继续）："); for(k=1;k<=L;k+) printf("%5d",Rk); getchar();printf("n"); num=0;QuickSort(1,L); break;case '5':Selectsort();break; case '6':Heap();break;case '0':ch1='n'break;default:printf("tt输入错误！请重新输入！ntt");if(ch2!=&#

39、39;0')if(ch2='2'|ch2='3'|ch2='4'|ch2='5'|ch2='6'|ch2='7'|ch2='8')printf("nt排序演示输出完毕！n"); printf("nt请按回车键返回主菜单.");q=getchar();if (q!='xA') getchar();ch1='n'void Insertsort()/直接插入排序int i,j,k,m=0; printf(&qu

40、ot;ntt尚未排序的数据为（回车继续）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=2;i<=L;i+)if(Ri<Ri-1) R0=Ri;j=i-1;while(R0<Rj) times+; changes+;Rj+1=Rj;j-;Rj+1=R0; changes+;m+; times+;printf("nn"); printf("t最终排序结果为：");for(i=1;i<=L;i+)p

41、rintf("%5d",Ri);printf("n"); printf("nt直接插入排序的比较次数为%d",times); printf("nt直接插入排序的移动次数为%d",changes); times=0; changes=0;void Shellsort() /希尔排序int i,j,gap,x,m=0,k; printf("nt尚未排序的数据为（回车继续）："); for(k=1;k<=L;k+)printf("%5d",Rk);getchar();prin

42、tf("n");gap=L/2;while (gap>0)for(i=gap+1;i<=L;i+) j=i-gap;while(j>0) times+;if (Rj>Rj+gap)x=Rj;Rj=Rj+gap;Rj+gap=x;j=j-gap; changes+; elsej=0;gap=gap/2;m+;printf("nn"); printf("t最终排序结果为：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); p

43、rintf("nt希尔排序的比较次数为%d",times); printf("nt希尔排序的移动次数为%d",changes); times=0; changes=0;void Bubblesort()/冒泡排序int i,j,k; int exchange; printf("ntt尚未排序的数据为（回车继续）：");for(k=1;k<=L;k+)printf("%5d",Rk);getchar();printf("n");for(i=1;i<=L;i+)exchange=FALS

44、E;for(j=L;j>=i+1;j-) times+; if(Rj<Rj-1) R0=Rj; Rj=Rj-1; Rj-1=R0; exchange=TRUE; changes+=3;if(exchange); printf("nn"); printf("t最终排序结果为：");for(i=1;i<=L;i+)printf("%5d",Ri);printf("n"); printf("nt冒泡排序的比较次数为%d",times); printf("nt冒泡排序的移动次

45、数为%d",changes); times=0; changes=0;int Partition(int i,int j) /快速排序int pirot=Ri;while(i<j)while(i<j&&Rj>=pirot)j-; times+;if(i<j)Ri+=Rj; changes+;while(i<j&&Ri<=pirot)i+; times+;if(i<j)Rj-=Ri; changes+;Ri=pirot;return i;void QuickSort(int low,int high)int pirotpos,k,i;if (low<high)pirotpos=Partition(low,high);num+;QuickSort(low,pirotpos-1); QuickSort(pirotpos+1,high);printf(&