内部排序算法的的性能分析.doc

1、 数据结构课程设计实验报告题 目 内部排序算法的的性能分析 学 院 数理与信息工程学院 专 业 计算机科学与技术 班 级 计科学122班 学 号 201259225236 学生姓名 黄文财 同组成员 金坚扬 李嘉良 指导教师 朱蓉 编写日期 2014.06.29 1 问题描述设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果。2 问题分析（1）用数组S来存放

2、系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。（2）利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。（3）在主函数中调用用户自定义函数，输出比较结果。（4）本程序是对几种内部排序算法的关键字进行性能分析的程序，它分为以下几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。3 数据结构描述31抽象数据类型定义Insertsort();初始条件：数组已经存在。基本思想：将一个记录插入到已经

3、排好序的有序列表中，从而得到了一个新的、记录新增1的有序表。 Shellsort();初始条件：数组已经存在。基本思想：先取定一个正整数d1n,把全部记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组内进行插入排序，然后取d2d1重复上述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。Bubblesort();初始条件：数组已经存在。基本思想：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。QuickSort(int low,int high)；初始条件：数组已经存在。基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），

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

5、；随机数的产生；调用子函数；（2）子函数模块：实现直接插入排序的抽象数据类型。 实现希尔排序的抽象数据类型 实现冒泡排序的抽象数据类型 实现快速排序的抽象数据类型 实现选择排序的抽象数据类型 实现5种排序数据对比 实现数据的更换 实现表长的更改最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数（关键字的交换记为三次移动），与所费时间。从而直观的判断各内部排序算法性能的优劣性。4 主要模块的算法描述 数据类型的定义(1)直接插入排序类型：void Insertsort();(2)希尔排序类型：void Shellsort();(3)冒泡排序类型：void Bubblesort();(4

6、)快速排序类型：void QuickSort(int low,int high);(5)选择排序类型：void Selectsort();(6) 5种排序数据对比：void AllsortCompare();(7) 实现数据的更换：void Changesort();(8) 实现表长的更改：void Changesortlong();下面是主程序的结构图和几个主要模块的流程图：开始 循环产生一组随机数将随机数保存在数组中算法比较选择排序快速排序起泡排序希尔排序插入排序记录关键字的比较次数和移动次数输出关键字的比较次数和移动次数结束 4.21主程序结构图 5 结果分析 关键字选择排序冒泡排序直插

7、排序快速排序希尔排序记录数比较次数最多最多较多最少较少较少移动次数较少最多较多较少较少比较次数最多最多较多较少较少较大移动次数较少最多较多较少较少6 心得体会通过本次课程设计，我对直接插入排序，希尔排序，选择排序等六种排序的概念有了一个新的认识，也慢慢地体会到了它们之间的奥妙。这次的课程设计，加强了我的动手，思考和解决问题的能力。巩固和加深了我对数据结构的理解，也让我懂得了理论与实际相结合是非常重要的，更让我进一步明白了“团结就是力量”这句话的含义。在整个设计过程中，构思是很花时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多是因为用错了方法，总是实现不了。同时在

8、设计过程中发现了自己的不足之处，对以前所学过的知识理解的不够深刻，掌握的不够透彻。根据我在课程设计中遇到的问题，我将在以后的学习过程中注意以下几点：1、多在实践中锻炼自己；2、写程序的过程中要考虑周到；3、在做设计的时候要有信心，有耐心，切勿浮躁。此次的课程设计得以顺利完成，与朱蓉老师的耐心指导和同学们的及时帮助是分不开的。当我在编写程序遇到难题时，是朱老师的耐心指导，我才可以突破一个个难关。在程序设计过程中，同学们给我的鼓励和帮助使我信心倍增。在此我再次向朱蓉老师和热心帮助我的同学表示深深的谢意。参考文献1朱蓉 刘小晶. 数据结构实验指导书2严蔚敏,吴伟民. 数据结构题集(C语言版).北京：

9、清华大学出版社，19993张铭. 数据结构与算法学习指导与习题解析. 北京：高教出版社.20094刘怀亮. 数据结构(C语言描述)习题与实验指导导. 北京：冶金出版社.2005.2附代码：#include #include #include #include time.h#define FALSE 0#define TRUE 1int l=1000;int s11001,R11001;long compare5,change5;double timess5;int num;double duration;clock_t start, finish; long times=0,changes=0

10、;void Insertsort();void Bubblesort();void QuickSort(int low,int high);void Shellsort();void Selectsort();void AllsortCompare();void Changesort();void Changesortlong();void Partition();void main()int i;char ch1,ch2,q;srand(unsigned)time(NULL);for(i=1;i=l;i+)si=rand()%10000;for(i=1;i=l;i+)Ri=si;ch1=y;

11、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* 7-更 换 表 中 数据-*n); printf(tt* 8-更 换 表 长-*n); printf(tt

12、* 0-返 回-*n);printf(tt*n);printf(tt目前表长为:%dntt请选择菜单号（0-8）:,l);scanf(%c,&ch2);getchar();switch(ch2)case 1:Insertsort();printf(=算法名称=比较次数=移动次数=时间=n);printf( 直接插入排序 %9ld %9ld %7lf n,compare1,change1,timess1);break;case 2:Shellsort();printf(=算法名称=比较次数=移动次数=时间=n);printf( 希尔排序 %9ld %9ld %7lf n,compare3,cha

13、nge3,timess3);break;case 3:Bubblesort();printf(=算法名称=比较次数=移动次数=时间=n);printf( 冒泡排序 %9ld %9ld %7lf n,compare2,change2,timess2);break; case 4:QuickSort(1,l);compare4=times;change4=changes;times=0;changes=0;printf(=算法名称=比较次数=移动次数=时间=n);printf( 快速排序 %9ld %9ld %7lf n,compare4,change4,timess4);break;case 5

14、:Selectsort();printf(=算法名称=比较次数=移动次数=时间=n);printf( 简单选择排序 %9ld %9ld %7lf n,compare0,change0,timess0);break;case 6:AllsortCompare();break;case 7:Changesort();break;case 8:Changesortlong();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=1)printf

15、(nt排序演示输出完毕！n);if(ch2=7)printf(nt更换数据完毕！n);if(ch2=8)printf(nt更换表长完毕！n); printf(nt请按回车键返回主菜单.);q=getchar();if (q!=xA)getchar();ch1=n;void Insertsort()/直接插入排序start = clock();int i,j,m=0;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+;compare1=ti

16、mes;change1=changes;times=0;changes=0;finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;timess1=duration;for(i=1;i0)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+;compare3=times;change3=changes;times=0; changes=0;finish = clock();

17、duration = (double)(finish - start) / CLOCKS_PER_SEC; timess3=duration;for(i=1;i=l;i+)Ri=si;void Bubblesort()/冒泡排序start = clock();int i,j; int exchange;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); compare2=times;change2=changes;times=0;changes=0;fin

18、ish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC; timess2=duration;for(i=1;i=l;i+)Ri=si;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

19、 high)start = clock();int pirotpos,i;if (lowhigh)pirotpos=Partition(low,high);num+;QuickSort(low,pirotpos-1);QuickSort(pirotpos+1,high);finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;timess4=duration;for(i=1;i=l;i+)Ri=si;void Selectsort() /选择排序start = clock();int i,j,h;for(i=1

20、;il;i+)h=i;for(j=i+1;j=l;j+)times+;if (RjRh)h=j;if(h!=j&h!=i)R0=Rh;Rh=Ri;Ri=R0;changes+=3;compare0=times;change0=changes;times=0;changes=0;finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;timess0=duration;for(i=1;i=l;i+)Ri=si;void AllsortCompare() Insertsort();Bubblesort();Quick

21、Sort(1,l);compare4=times;change4=changes;times=0;changes=0;Shellsort();Selectsort();printf(n);printf(=算法名称=比较次数=移动次数=时间=n);printf(1简单选择排序 %9ld %9ld %7lf n,compare0,change0,timess0);printf(2直接插入排序 %9ld %9ld %7lf n,compare1,change1,timess1);printf(3冒泡排序 %9ld %9ld %7lf n,compare2,change2,timess2);print

22、f(4希尔排序 %9ld %9ld %7lf n,compare3,change3,timess3);printf(5快速排序 %9ld %9ld %7lf n,compare4,change4,timess4);printf(n);void Changesort()char c;int i,j;printf(nnnnnttt修 改 数 据 操 作n);printf(tt*n);printf(tt* 1-随机修改数据-*n);printf(tt* 2-修改数据为正序 -*n);printf(tt* 3-修改数据为逆序 -*n);printf(tt*n);printf(tt目前表长为:%dntt

23、请选择菜单号（1-3）:,l);scanf(%c,&c);getchar();switch(c)case 1:for(i=1;i=l;i+)si=rand()%10000;for(i=1;i=l;i+)Ri=si;break;case 2:for(i=1;i=l;i+)si=i;for(i=1;i=l;i+)Ri=si;break;case 3:for(i=1,j=l;i=l;i+,j-)si=j;for(i=1;i=l;i+)Ri=si;break;default:printf(tt输入错误！请重新输入！ntt);void Changesortlong()char c;int i;print

24、f(nnnnnttt修 改 表 长 操 作n);printf(tt*n);printf(tt* 1-修改表长为2000 -*n);printf(tt* 2-修改表长为4000 -*n);printf(tt* 3-修改表长为6000 -*n);printf(tt* 4-修改表长为8000-*n);printf(tt* 5-修改表长为10000 -*n);printf(tt* 6-自定义修改表长-*n);printf(tt*n);printf(tt目前表长为:%dntt请选择菜单号（1-6）:,l);scanf(%c,&c);getchar();switch(c)case 1:l=2000;break;case 2:l=4000;break;case 3:l=6000;break;case 4:l=8000;break;case 5:l=10000;break;case 6:printf(tt*输入表长*(110000):);scanf(%d,&l);break;default:printf(tt输入错误！请重新输入！ntt);for(i=1;i=l;i+)si=rand()%10000;for(i=1;i=l;i+)Ri=si;word文档 可自由复制编辑