排序算法试验报告

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

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

3、;i+)ai=(int)(Math.random()*100000);2.计算时间的类Date通过它的对象d1的getTime()得到当前时间，再得到排序完成时的时间，相减得到排序所花的时间.Dated1=newDate();T=d2.getTime()-d1.getTime()3:排序算法：其它count均表示排序中比较的次数插入排序主要算法如下intcount=0;intc=newintb.length;c0=b0;intj;for(inti=1;i<c.length;i+)(for(j=i-1;j>=0&&bi<cj;j-)count+;cj+1=cj;

4、count+;cj+1=bi;选择排序主要算法：intcount=0;for(inti=0;i<b.length;i+)intk=i;for(intj=i+1;j<b.length;j+)count+;if(bj<bk)k=j;if(k!=i)intl;l=bi;bi=bk;bk=l;合并排序：staticintmerge(inta,intst,intce,intfi)intcount=0;/a表示数组,st表示要排序的数据的起点,ce表示第一部分的终点也是第二部分的起点,fi表示第二部份的终点inti=st;intj=ce;intcp=0;由于数组c从0开始，而a是从st开

5、始，并不一定是0.故要通过cp来表示c的第cp个值.intc=newintfi-st;for(;i<ce;i+)for(;j<fi;j+)if(ai>aj)count+;ccp=aj;cp+;elsebreak;ccp=ai;cp+;，主要由自己的理解来实现若j的值还小于fi则继续把j到fi的值复制给c.此处也与书上的不同for(;j<fi;j+)ccp=aj;cp+;把得到的值复制到a数组上for(intk=0;k<c.length;k+)ast=ck;st+;returncount;快速排序：用的方法与书上略有不同，主要通过spilt直接进彳f递归.stati

6、cintspilt(inta,intlow,inthigh)intcount=0;inti=low;intx=alow;for(intj=low+1;j<=high;j+)if(aj<=x)count+;i=i+1;if(i!=j)inttemp=ai;ai=aj;aj=temp;inttemp=alow;alow=ai;ai=temp;intw=i;if(low<high)if(w-1>low)count=count+spilt(a,low,w-1);此处的if语句可以减少很多不必要的排序,例如只剩下一个数字时就不必再用spilt来排序了.if(w+1<high

7、)count=count+spilt(a,w+1,high);returncount;二:实验数据及其结果(可用图表形式给出)：排序个数插入排序选择排序合并排序快速排序堆排序比较次数时间比较次数时间比较次数时间比较次数时间比较次数时间10002464153毫秒4995002毫秒42921毫秒60420毫秒53361毫秒20009879054毫秒19990005毫秒138950毫秒125021毫秒172511毫秒300022212537毫秒44985009毫秒289111毫秒180721毫秒357381毫秒4000397480712毫秒799800016毫秒500871毫秒277630毫秒613

8、891毫秒5000633074017毫秒1249750024毫秒767192毫秒316730毫秒941190毫秒6000900082226毫秒1799700033毫秒1095151毫秒388761毫秒1343651毫秒70001236164934毫秒2449650044毫秒1487921毫秒527861毫秒1820491毫秒80001619570146毫秒3199600059毫秒1952612毫秒547160毫秒2374561毫秒90002031273058毫秒4049550075毫秒2473952毫秒781171毫秒3004441毫秒100002472051070毫秒4999500091毫秒

9、3057281毫秒802731毫秒3708431毫秒110002993784884毫秒60494500113毫秒3705174毫秒899601毫秒4488411毫秒1200036256786104毫秒71994000133毫秒4422322毫秒1077071毫秒5350302毫秒1300042587471120毫秒84493500155毫秒5204922毫秒1028601毫秒6291741毫秒1400049063373139毫秒97993000177毫秒6058062毫秒1253641毫秒7311911毫秒1500056280216161毫秒112492500201毫秒6985463毫秒134

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