排序算法试验报告材料

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

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

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

4、or(int i=1;i=0&bicj;j-) count+;cj+1=cj;count+;cj+1=bi;选择排序主要算法 :int count=0;for(int i=0;ib.length;i+)精彩文档实用标准文案 int k=i;for(int j=i+1;jb.length;j+)count+;if (bjbk) 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(;ice;i+)for(;jaj) count+;ccp=aj;cp+;else break;ccp=ai;cp+;/ 若 j 的值还小于 fi 则继续把 j 到 fi 的值复制给 c.此处也与书上的不同 , 主要由自己的理解来实现精彩文档实用标准文案for(;jfi;j+)ccp=aj;cp+;/ 把得到的值复制到 a 数组上for(

6、int k=0;kc.length;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;j=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 语句可

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

8、1 毫秒300022212537 毫秒44985009 毫秒289111 毫秒18072 1毫秒357381 毫秒4000397480712 毫秒799800016 毫秒500871 毫秒27763 0毫秒613891 毫秒5000633074017 毫秒1249750024 毫秒767192 毫秒31673 0毫秒941190 毫秒6000900082226 毫秒1799700033 毫秒1095151 毫秒38876 1毫秒1343651 毫秒70001236164934 毫秒2449650044 毫秒1487921 毫秒52786 1毫秒1820491 毫秒80001619570146

9、毫秒3199600059 毫秒1952612 毫秒54716 0毫秒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 毫秒1300042587471

10、120 毫秒84493500155 毫秒5204922 毫秒102860 1毫秒6291741 毫秒1400049063373139 毫秒97993000177 毫秒6058062 毫秒125364 1毫秒7311911 毫秒1500056280216161 毫秒112492500 201 毫秒6985463 毫秒134152 2毫秒8414923 毫秒1600064205137185 毫秒127992000 228 毫秒7994102 毫秒135362 1毫秒9604001 毫秒1700072750562206 毫秒144491500 258 毫秒9068383 毫秒144717 1毫秒10

11、87013 2毫秒1800080846587231 毫秒161991000 288 毫秒1020136 3毫秒164631 2毫秒1221699 2毫秒1900090537142264 毫秒180490500 321 毫秒1139757 5毫秒168298 2毫秒1364230 2毫秒三:实验结果分析及结论：精彩文档实用标准文案实验结果表明 ,选择排序用时普遍比其它算法大,自顶向上合并排序时间普遍较少,尤其是当数据量变得很大的时候 ,选择排序的速度变得远远不及自顶向上合并排序算法,大出好几百倍 .另外 ,插入排序在当数据量变大时花费的时间也变得很长.快速排序和堆排序处于不确定的情况 ,不稳定性比较明显 .但是是一种比较快的算法 .四:实验自我评价及心得体会：通过本实验 ,我发现以前经常使用的冒泡排序 ,选择排序等排序方法在遇到大量的数据的时候显示出来的