内部排序算法的性能分析

1、数据结构课程设计报告设计题目：内部排序算法的性能分析 专 业 通信工程 班 级 0803 学 生 潘志威 学 号 2008115020312 指导教师 孙玉霞 起止时间 2011-2-212011-2-27 湖北师范学院 2011 年 第一 学期目录1需求分析21.1、选题要求21.2、选题的意义及背景21.3、课程设计目标32概要设计32.1原始数据32.2输出数据32.3数据处理43 算法描述53.1逻辑结构及存储结构53.2系统的模块划分及模块功能53.2.1主程序模块53.2.2可排序表单元模块63.3程序代码64 调试分析15 测试结果25.1测试用例及选择原因25.2 测试结果35

2、.3 结论35.4 结果分析36 心得体会47 参考文献51需求分析1.1、选题要求对各种排序算法进行定量的性能分析。1.2、选题的意义及背景排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种内部排序算法进行比较，能使我们更好的

3、掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1.3、课程设计目标本课程设计对以下内部排序算法进行比较：起泡排序、直插排序、选择排序、快速排序、堆排序。待排序表的元素关键字为整数，用不同的测试数据做测试比较。比较的指标为关键字的比较次数和关键字的移动次数。最后用图、表格数据汇总数据，以便对这些内部排序算法进行性能分析。 2概要设计2.1原始数据用户输入记录的个数，数据由随机数产生器生成。2.2输出数据产生的随机数分别用

4、起泡排序、直插排序、选择排序、快速排序、归并排序这些排序方法进行排序，输出关键字的比较次数和移动次数。2.3数据处理主程序产生1组随机数起泡排序直插排序快速排序堆排序选择排序记录关键字的比较次数和移动次数将随机数保存在数组中循环50次输出关键字的比较次数、移动次数的平均值3 算法描述3.1逻辑结构及存储结构以顺序表为存储结构typedef structkeytype key;datatype;3.2系统的模块划分及模块功能mainselectsortbubblesortinsertsortquicksortheapsortoutput系统分为两个模块3.2.1主程序模块void main()3

5、.2.2可排序表单元模块冒泡排序：void bubblesort(datatype a,int n)插入排序：void insertsort(datatype a,int n)直接选择排序：void selectsort(datatype a,int n)快速排序：void quicksort(datatype a,int low,int high)希尔排序：void shellsort(datatype a,int n,int d,int numofd)堆排序：void creatheap(datatype a,int n,int h)3.3程序代码5头文件：typedef int keyt

6、ype;typedef structkeytype key;datatype;static long int count1=0,count2=0;/*冒泡排序*/void bubblesort(datatype a,int n)int i,j,flag=1;datatype temp;for(i=1;i<n&&flag=1;i+)flag=0;for(j=0;j<n-i;j+)if(aj.key>aj+1.key)count2+;flag=1;temp=aj;count1+;aj=aj+1;count1+;aj+1=temp;count1+;/*插入排序*/v

7、oid insertsort(datatype a,int n)int i,j;datatype temp;for(i=0;i<n-1;i+)temp=ai+1;j=i;while(j>-1&&temp.key<aj.key)count2+;aj+1=aj;count1+;j-;aj+1=temp;count1+;/*选择排序*/void selectsort(datatype a,int n)int i,j,sm;datatype temp;for(i=0;i<n-1;i+)sm=i;/设第i个数据元素关键字最小for(j=i+1;j<n;j+)

8、/寻找关键字最小的数据元素if(aj.key<asm.key)sm=j;/记住最小元素的下标count2+;if(sm!=i)/当最小元素的下标不为i时交换位置temp=ai;count1+;ai=asm;count1+;asm=temp;count1+;/*快速排序*/void quicksort(datatype a,int low,int high)/用递归方法对数据元素进行快速排序int i=low,j=high;datatype temp=alow;/取第一个元素为标准数据元素while(i<j)while(i<j&&temp.key<=aj.

9、key)j-;/在数组的右端扫描count2+;if(i<j)ai=aj;count1+;i+;while(i<j&&ai.key<temp.key)i+;/在数组的左端扫描count2+;if(i<j)aj=ai;count1+;j-;ai=temp;count1+;if(low<i) quicksort(a,low,i-1);/对左端子集合进行递归if(i<high) quicksort(a,j+1,high);/对右端子集合进行递归/*希尔排序*/void shellsort(datatype a,int n,int d,int num

10、ofd)/用希尔排序法对元素a0an-1排序，d0dm为希尔增量值int i,j,k,m,span;datatype temp;for(m=0;m<numofd;m+)span=dm;for(k=0;k<span;k+)/共span个小组for(i=k;i<n-span;i=i+span)temp=ai+span;count1+;j=i;while(j>-1&&temp.key<aj.key)count2+;aj+span=aj;count1+;j=j-span;aj+span=temp;count1+;/*堆排序*/void creatheap(

11、datatype a,int n,int h)int i,j,flag;datatype temp;i=h;/i为要建堆的二叉树根结点下标j=2*i+1;/ j为i的左孩子结点的下标temp=ai;count1+;flag=0;/沿左右孩子中值较大者重复向下筛选while(j<n&&flag!=1)if(j<n-1&&aj.key<aj+1.key)j+;count2+;if(temp.key>aj.key)flag=1;/标记结束筛选条件count2+;否则把aj上移else/ai=aj;count1+;i=j;j=2*i+1;ai=t

12、emp;count1+;void initcreatheap(datatype a,int n)int i;for(i=(n-1)/2;i>=0;i-)creatheap(a,n,i);void heapsort(datatype a,int n)int i,count=0;datatype temp;initcreatheap(a,n);/初始化创建最大堆for(i=n-1;i>0;i-)/当前最大堆个数每次递减1temp=a0;count1+;a0=ai;count1+;ai=temp;count1+;creatheap(a,i,0);/调整根结点满足最大堆主程序：#inclu

13、de<windows.h>#include<stdio.h>#include"sort.h"void main()datatype r10000,r10000,a1000,b1000,c1000,e1000,f1000;int i,j,s; int p;int n; char yn; int d5=500,100,50,10,1; printf("请输入产生随机数个数n"); scanf("%d",&p); n=p; while(1) int k=0; for(i=0;i<(p/10);i+) s

14、rand(i+gettickcount(); for(j=0;j<10;j+) rk.key=rand(); k+; printf("%8d",rk-1.key); printf("n*n");printf("1.测试冒泡排序n");printf("2.测试直接插入排序n");printf("3.测试选择排序n");printf("4.测试快速排序n");printf("5.测试希尔排序n");printf("6.测试堆排序n")

15、;printf("*n");label_1:printf("请选择"); scanf("%d",&s);switch(s)case 1 : count1=0;count2=0;for(i=0;i<10000;i+)ri.key=ri.key;bubblesort(r,n);printf("冒泡排序移动次数%dn",count1);printf("冒泡排序比较次数%dn",count2);break;case 2:count1=0;count2=0;for(i=0;i<1000

16、0;i+)ai.key=ri.key;insertsort(a,n);printf("直接插入排序移动次数%dn",count1);printf("直接插入排序比较次数%dn",count2);break; case 3:count1=0;count2=0;for(i=0;i<10000;i+)bi.key=ri.key; selectsort(b,n);printf("选择排序移动次数%dn",count1);printf("选择排序比较次数%dn",count2); break;case 4:count1

17、=0;count2=0;for(i=0;i<10000;i+)ci.key=ri.key;quicksort(c,0,n-1);printf("快速排序移动次数%dn",count1);printf("快速排序比较次数%dn",count2);break;case 5:count1=0;count2=0;for(i=0;i<10000;i+)ei.key=ri.key; shellsort(e,n,d,5);printf("希尔排序移动次数%dn",count1);printf("希尔排序比较次数%dn"

18、;,count2);break;case 6:count1=0;count2=0;for(i=0;i<10000;i+)fi.key=ri.key;heapsort(f,n,0);printf("堆排序移动次数%dn",count1);printf("堆排序比较次数%dn",count2);break;default:printf("选择出错!n"); getchar(); printf("是否继续测试其他测试方法(y/n):n"); scanf("%c",&yn); if(yn=

19、'y'|yn='y') goto label_1; printf("是否换数据重新测试(y/n):n"); getchar(); scanf("%c",&yn); if(yn!='y'&&yn!='y') break; 4 调试分析进入调试界面后选择要测试排序算法的序号，比如选择1，就对随机产生的1000个数据用冒泡法进行测试，结果是冒泡排序执行次数726450，然后选择是否继续，若继续选择y，若退出测试选择n。5 测试结果5.1测试用例及选择原因记录数分别输入100

20、0、10000、100000，之所以想用这三个记录数测试，是想测试用选择排序、起泡排序、直插排序、快速排序、归并排序这五种排序方法，在记录较小和较大时，关键字的比较次数和移动次数，用以直观的分析它们的性能。5.2 测试结果记录数的个数关键字选择排序起泡排序直插排序快速排序堆排序1000比较次数368194036移动次数186812182310000比较次数4851980199624688移动次数28173941564327409100000比较次数49850199800199984879984移动次数2974749592175354476854335.3 结论关键字选择排序起泡排序直插排序快速

21、排序堆排序记录数比较次数较少最多最少较少较少较小移动次数较少最多较少较少较少比较次数较少最多最少较少较少较大移动次数最少最多较多较少较少5.4 结果分析（1）选择排序的比较次数较少且为定值，但由于它在排序过程中要先查询、再安置，所以性能上不够稳定。（2）起泡排序的比较次数和移动次数在这五种排序方式中最多，所以起泡排序的排序性能相对于其他排序要低好多。（3）直插排序的比较次数和移动次数相比较于其他几种排序次数要少，所以效率相比较而言较高，性能较高，且较稳定。从整体上来讲性能较其他几种排序较高。（4）快速排序在这几种排序当中从比较次数较少的，移动次数多于选择排序但低于其他三种排序，且其过程是先定一个