排序算法实验报告材料

1、实验课程：算法分析与设计实验名称：几种排序算法的平均性能比较(验证型实验)实验目标：(1) 几种排序算法在平均情况下哪一个更快。(2) 加深对时间复杂度概念的理解。实验任务：(1 ) 实现几种排序算法( selecti on sort, in serti on sort,bottomupsort,quicksort,堆排序)对于快速分类，SPLIT中的划分元素采用三者 A(low )，A(high )，A( low+ high )/2) 中其值居中者。(2 )随机产生20组数据(比如n =5000 i, 1 <i<20 )。数据均属于范围(0, 105 )内的整 数。对于同一组数据

2、，运行以上几种排序算法，并记录各自的运行时间(以毫秒为单位)。(3) 根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境：PC; C/C+等编程语言。实验主要步骤：(1) 明确实验目标和具体任务；(2) 理解实验所涉及的几个分类算法；(3) 编写程序实现上述分类算法；(4) 设计实验数据并运行程序、记录运行的结果;(5) 根据实验数据及其结果得出结论；(6) 实验后的心得体会。一:问题分析(包括问题描述、建模、算法的基本思想及程序实现的技巧等)1:随机生成n个0到100000的随机数用来排序的算法如下.for(int n=1000;n<20000;n

3、+=1000)int a=new intn;for(int i=0;i<n;i+)ai=(int) (Math.random()*100000);，相减得到排2.计算时间的类Date通过它的对象di的getTime()得到当前时间，再得到排序完成时的时间 序所花的时间.Date d仁 new Date();T=d2.getTime()-d1.getTime()3:排序算法：其它count均表示排序中比较的次数.插入排序主要算法如下int count=0;int c=new intb .1 ength;c0=b0;int j;for(int i=1;i<c.length;i+)for

4、(j=i-1;j>=0&&bi<cj;j-) count+;cj+1=cj;count+;cj+1=bi;选择排序主要算法：int count=0;for(int i=0;i<b .1 ength;i+) int k=i;for(int j=i+1;j<b .1 ength;j+)count+;if (bj<bk)k=j;if(k!=i)int l;l=bi;bi=bk;bk=l;合并排序：static int merge(int a,int st,int ce,int fi)int count=0;/a表示数组,st表示要排序的数据的起点，ce表

5、示第一部分的终点也是第二部分的起点,fi表示第二部份的终点int i=st;int j=ce;int cp=0;/由于数组c从0开始，而a是从st开始，并不一定是0.故要通过cp来表示c的第cp个值.int c=new intfi-st;for(;i<ce;i+)for(;j<fi;j+)if(ai>aj) count+;ccp=aj;cp+;else break;ccp=ai;cp+;/若j的值还小于fi则继续把j到fi的值复制给c.此处也与书上的不同，主要由自己的理解来实现for(;jvfi;j+)c【cp=aj;cp+;/把得到的值复制到 a数组上for(int k=O

6、;k<c .1 ength;k+)ast=ck;st+;return count;快速排序：用的方法与书上略有不同，主要通过spilt直接进行递归static int spilt(int a,int low,int high)int count=0;int i=low;int x=alow;for(int j=low+1;jv=high;j+)if(aj<=x)count+;i=i+1;if(i!=j)int temp=ai;ai=aj;aj=temp;int temp= alow; alow=ai; ai=temp;int w=i;if(low<high)/此处的if语句可

7、以减少很多不必if(w-1>low)count=count+spilt(a,low,w-1);要的排序，例如只剩下一个数字时就不必再用spilt来排序了if(w+1<high)count=count+spilt(a,w+1,high);return count;:实验数据及其结果(可用图表形式给出)排序个数插入排序选择排序 比较次数时间合并排序比较次数时间快速排序比较次数时间堆排序比较次数时间比较次数时间10002464153毫秒4995002毫秒42921毫秒6042 0毫秒53361毫秒20009879054毫秒19990005毫秒138950毫秒12502 1毫秒172511

8、毫秒300022212537毫秒44985009毫秒289111毫秒18072 1毫秒357381毫秒4000397480712毫秒799800016毫秒500871毫秒277630毫秒613891毫秒5000633074017毫秒1249750024毫秒767192毫秒316730毫秒941190毫秒6000900082226毫秒1799700033毫秒1095151毫秒38876 1毫秒1343651毫秒70001236164934毫秒2449650044毫秒1487921毫秒52786 1毫秒1820491毫秒80001619570146毫秒3199600059毫秒1952612毫秒54

9、7160毫秒2374561毫秒90002031273058毫秒4049550075毫秒2473952毫秒78117 1毫秒3004441毫秒100002472051070毫秒4999500091毫秒3057281毫秒80273 1毫秒3708431毫秒110002993784884毫秒60494500113毫秒3705174毫秒89960 1毫秒4488411毫秒1200036256786104毫秒71994000133毫秒4422322毫秒107707 1毫秒5350302毫秒1300042587471120毫秒84493500155毫秒5204922毫秒102860 1毫秒6291741毫

10、秒1400049063373139毫秒97993000177毫秒6058062毫秒125364 1毫秒7311911毫秒1500056280216161毫秒112492500 201 毫秒6985463毫秒1341522毫秒8414923毫秒1600064205137185毫秒127992000 228 毫秒7994102毫秒135362 1毫秒9604001毫秒1700072750562206毫秒144491500 258 毫秒9068383毫秒144717 1毫秒10870132毫秒1800080846587231毫秒161991000 288 毫秒10201363毫秒1646312毫秒1

11、2216992毫秒1900090537142264毫秒180490500 321 毫秒11397575毫秒1682982毫秒13642302毫秒三:实验结果分析及结论:实验结果表明，选择排序用时普遍比其它算法大，自顶向上合并排序时间普遍较少，尤其 是当数据量变得很大的时候，选择排序的速度变得远远不及自顶向上合并排序算法，大出好几百倍另外,插入排序在当数据量变大时花费的时间也变得很长.快速排序和堆排序处于不确定的情况，不稳定性比较明显但是是一种比较快的算法四:实验自我评价及心得体会：通过本实验，我发现以前经常使用的冒泡排序，选择排序等排序方法在遇到大量的数据的时候显示出来的严重的不足，而自底向上合