实验报告内部排序算法比较.doc

实验报告 内部排序算法比较题目：内部排序算法比较排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较一.问题分析和总体设计adt orderablelist 数据对象：d=ai| aiintegerset,i=1,2,n,n0 数据关系：r1=ai-1，ai|ai-1, aid, i=1,2,n 基本操作：initlist(n) 操作结果：构造一个长度为n，元素值依次为1，2，n的有序表。randomizel(d,isinverseorser) 操作结果：随机打乱bubblesort( ) 操作结果：进行起泡排序insersort( ) 操作结果：进行插入排序selectsort( ) 操作结果：进行选择排序quicksort( ) 操作结果：进行快速排序heapsort( ) 操作结果：进行堆排序listtraverse(visit( ) 操作结果：依次对l种的每个元素调用函数visit( ) adt orderablelist待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果.要求对结果进行分析.二.详细设计1、起泡排序bubblesort(struct rec r,int n)int i,j;struct rec w;unsigned long int compare=0,move=0;for(i=1;i=i+1;j-) if(rj.keyrj-1.key) w=rj; rj=rj-1; rj-1=w; move=move+3; compare+; printf(nbubblesort compare= %ld,move= %ldn,compare,move);2、直接插入排序insertsort(struct rec r,int n)int i,j;unsigned long int compare=0,move=0;for(i=2;i=n;i+) compare+; r0=r; move+; j=i-1; while(r0.key3、简单选择排序selectsort(struct rec r,int n)unsigned long int compare=0,move=0;int i,j,k;struct rec w;for(i=1;i=n-1;i+) k=i; for(j=i+1;jrk.key) k=j; compare+; w=r; r=rk; rk=w; move=move+3; printf(nselectsort compare= %ld,move= %ldn,compare,move);4、快速排序q(struct rec r,int s,int t)int i=s,j=t;if(si&rj.key=r0.key) j-; +a; if(ij) r=rj; i+; c+; while(ij&r.key=r0.key) i+; +a; if(ij) rj=r; j-; c+; while(ij);r=r0;c+;q(r,s,j-1);q(r,j+1,t);5. 堆排序sift(struct rec r,int l,int m)int i,j;struct rec w;i=l; j=2*i;w=r;while(j=m) if(jm&rj.keyrj+1.key) j+; if(w.key=1;i-) a=sift(r,i,n); compare+; move+; for(i=n;i=2;i-) w=r; r=r1; r1=w; a=sift(r,1,i-1); compare+=a; move+=a; 三.实验结果：1.实验测试结果如下： 3.对排序算法的总结：从实验结果知道：对于比较次数：起泡排序次数最多，选择排序第二多且与数据是否基本有序无关，插入排序第三多。对于移动次数：起泡排序次数最多，插入排序第二多，希尔排序约为快速排序的两倍。对于时间：起泡排序花费的时间最多，插入排序第二多，选择排序第三多，快速排序，希尔排序还有堆排序这三种排序时间都花很少。起泡排序和插入排序随着数组的混乱程度的增加，花的时间也会增加。对于不同程度的混乱程度，选择排序的时间长短相差不大。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。四、实验心得：通过本次实验，对各种算法有了深刻的了解。知道在什么情况下该用什么算法。(1)若n较小(如n50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动