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

. .课程设计(论文)题 目名称 几种常见的排序算法的实现与性能分析课 程 名 称数据构造课程设计学生XX学号系 、专 业 信息工程系、通信工程 指导教师2012年12月23日摘 要设计一个测试程序比较起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数。运用多种自定义函数，通过在主函数中调用自定义函数，实现其功能，最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数关键字的交换记为三次移动。从而直观的判断各部排序算法性能的优劣性。关键词：起泡排序；直接排序；简单项选择择排序；快速排序；希尔排序；堆排序；部排序；直观；比较次数；移动次数. .word.zl. .目录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分24 详细设计341数据类型的定义342主要模块的算法描述35 测试分析86 课程设计总结12参考文献12附录源程序清单13. .word.zl. .1 问题描述设计一个测试程序比较起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数关键字交换记为3次移动。最后输出比较结果。2 需求分析1用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。2利用全局变量times和changes来分别统计起泡排序、直接排序、简单项选择择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。3在主函数中调用用户自定义函数，输出比较结果。4本程序是对几种部排序算法的关键字进展性能分析的程序，它分为以下几个局部：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。3 概要设计31抽象数据类型定义排序数据类型定义：ADT paixu数据对象：D=aij|aij属于1，2，3,i,j0数据关系：R=|ai-1,aiD，i=2,.,n根本操作：Insertsort();初始条件：数组已经存在。根本思想：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。Shellsort();初始条件：数组已经存在。根本思想：先取定一个正整数d1n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组进展插入排序，然后取d2d1重复上述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。Bubblesort();初始条件：数组已经存在。根本思想：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。QuickSort(int low,int high)；初始条件：数组已经存在。根本思想：在待排序的n个记录中任取一个记录通常取第一个记录，以该记录的键值为基准用交换的法将所有记录分成两局部，所有键值比它小的安置在一局部，所有键值比它大的安置在另一局部，并把该记录排在两局部的中间，也就是该记录的最终位置。这个过程称为一趟快速排序。然后分别对所划分的两局部重复上述过程，一直重复到每局部只有一个记录为止排序完成。Selectsort();初始条件：数组已经存在。根本思想：每次从待排序的记录中选出键值最小或最大的记录，顺序放在已排序的记录序列的最后，直到全部排完。对待排序的文件进展n-1趟扫描，第i趟扫描选出剩下的n-i+1个记录，并与第i个记录交换。Heap();初始条件：数组已经存在。根本思想：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列称为初建堆，这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重建堆，便得到次小键值，如此反复进展，知道把全部键值排好序为止。ADT排序32模块划分本程序包括两个模块：1主程序模块void main()初始化；随机数的产生；调用子函数；2子函数模块：实现直接插入排序的抽象数据类型。 实现希尔排序的抽象数据类型。 实现冒泡排序的抽象数据类型。 实现快速排序的抽象数据类型。 实现选择排序的抽象数据类型。 实现堆排序的抽象数据类型。最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数关键字的交换记为三次移动。从而直观的判断各部排序算法性能的优劣性。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主要模块的算法描述下面是主程序的构造图和几个主要模块的流程图：开场循环产生一组随机数将随机数保存在数组中堆排序选择排序快速排序起泡排序希尔排序插入排序记录关键字的比较次数和移动次数输出关键字的比较次数和移动次数完毕 4.21主程序构造图 开场输入要排序的一组元素i=1,j=1定义临时中间变量k，并赋初值i元素总个数Nii+1j第j+1个元素YN利用k交换第j个元素和第j+1个元素Y输出比较次数和移动次数完毕4.22冒泡排序关键字比较次数和移动次数的流程图开场输入要排序的一组元素i=1，j=1定义临时中间变量h，并赋初值i元数总个数N做第i趟排序Yi=i+1在无序区Ri-n中选h最小记录Rhh记下目前找到的最小关键字所在的位置交换Ri和Rh输出比较次数和移动次数完毕4.23选择排序关键字比较次数和移动次数的流程图开场输入要排序的一组元素定义临时中间变量k，并赋初值将二叉树转换成堆i=总元素个数-1i=1N将堆的根植和最后一个值交换Yi-,k+输出比较次数和移动次数完毕4.24堆排序关键字比较次数和移动次数的流程图5 测试分析进展了99趟排序后，得到了最终的排序结果，并且也知道了直接插入排序的比较次数和移动次数了解了直接插入排序的性能后，下面是希尔排序的性能比较：了解了希尔排序的性能后，下面是冒泡排序的性能比较：了解了冒泡排序的性能后，下面是快速排序的性能比较：了解了快速排序的性能后，下面是选择排序的性能比较：了解了选择排序的性能后，下面是堆排序的性能比较：以上就是对六种排序算法的一种演示，经过观察和分析我们可以比较六种排序的性能。6 课程设计总结通过本次课程设计，我对直接插入排序，希尔排序，选择排序等六种排序的概念有了一个新的认识，也慢慢地体会到了它们之间的微妙。这次的课程设计，加强了我的动手，思考和解决问题的能力。稳固和加深了我对数据构造的理解，也让我懂得了理论与实际相结合是非常重要的，更让我进一步明白了“团结就是力量这句话的含义。在整个设计过程中，构思是很花时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多是因为用错了法，总是实现不了。同时在设计过程中发现了自己的缺乏之处，对以前所学过的知识理解的不够深刻，掌握的不够透彻。根据我在课程设计中遇到的问题，我将在以后的学习过程中注意以下几点：1、多在实践中锻炼自己；2、写程序的过程中要考虑到；3、在做设计的时候要有信心，有耐心，切勿急躁。此次的课程设计得以顺利完成，与黄同成教师的耐心指导和同学们的及时帮助是分不开的。当我在编写程序遇到难题时，是黄教师的耐心指导，我才可以突破一个个难关。在程序设计过程中，同学们给我的鼓励和帮助使我信心倍增。在此我再次向黄同成教师和热心帮助我的同学表示深深的意。参考文献1 黄同成，黄俊民，董建寅数据构造M：中国电力，20212 董建寅，黄俊民，黄同成数据构造实验指导与题解M：中国电力，20213 蔚敏，伟民. 数据构造C语言版M. ：清华大学，20024 振鹏，晓莉，郝杰数据构造M：中国铁道，2003附录源程序清单#include #include #include #include #define L 100#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 main()/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)printf(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(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(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!=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(ntt尚未排序的数据为回车继续：);for(k=1;k=L;k+)printf(%5d,Rk);getchar();printf(n);for(i=2;i=L;i+)if(RiRi-1) R0=Ri;j=i-1;while(R0Rj) times+; 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;void Shellsort() /希尔排序int i,j,gap,x,m=0,k; printf(nt尚未排序的数据为回车继续：); for(k=1;k0)for(i=gap+1;i0) times+;if (RjRj+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(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=i+1;j-) times+; if(RjRj-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冒泡排序的移动次数为%d,changes); times=0; changes=0;int Partition(int i,int j) /快速排序int pirot=Ri;while(ij)while(i=pirot)j-; times+;if(ij)Ri+=Rj; changes+;while(ij&Ri=pirot)i+; times+;if(ij)Rj-=Ri; changes+;Ri=pirot;return i;void QuickSort(int low,int high)int pirotpos,k,i;if (lowhigh)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);printf(nt快速排序的比较次数为%d,times);printf(nt快速排序的移动次数为%d,changes);times=0;changes=0;void Selectsort() /选择排序int 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 (RjRh)h=j;if(h!=j)R0=Rh;Rh=Ri;Ri=R0; changes+=3; 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;void CreateHeap(int root,int index)/建堆int j,temp,finish;j=2*root;temp=Rroot;finish=0;while (j=index&finish=0)if (jindex)if (Rj=Rj) finish=1; /堆建立完成 times+; elseRj/2=Rj;/父结点=当前结点j=j*2; changes+;Rj/2=temp; /父结点=root值void HeapSort()int 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);getchar();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;教育之通病是教用脑的人不用手，不教用手的人用脑，所以一无所能。教育革命的对策是手脑联盟，结果是手与脑的力量都可以大到不可思议。. .word.zl.