五种排序算法分析课件

1、深圳大学实验报告课程名称：算法分析与复杂性理论实验项目名称:实验一排序算法性能分析学院：计算机与软件学院专业：软件工程指导教师:皿报告人:赖辉学号:班级：软工学术型实验时间：2015-10-15实验报告提交时间：2015-11-24教务部制.实验目的1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。二.实验步骤与结果实验总体思路：根据实验要求，需要用while循环控制用户选择相应算法(选择通过switch实现)或者选择入0跳出while循环，退出程序。Switch中选择相应的算法后需要通过一个for(in

2、tj=0;j<5;j+)循环更改数组大小MAX勺值(MAX*=10),从而控制输入不同问题规模的耗时。再通过一个for(inti=0;i<20;i+)循环控制20组随机数组。为了使得程序输出更加直观，部分数据后面没有输出。相应结果和过程如下所示(代码和结果如下图所示)。各排序算法的实现及实验结果：1、随机数产生代码1:srand(unsigned)time(NULL);Fori=0to19randNum(MAX,array);当问题规模较小时，生成随机函数randNum()在for循环下运行时间短，每次产生的随语句放在for循环外面，就产生了 20机数组都是一样的，将srand(u

3、nsigned)time(NULL)组不同的随机数组。S匚，11一团,配曰屁兑通0rD，上匕<叩叫/算i.exeL选择排序2.冒牖蟀器翱磐褪序5.插入排序山退出程序1386644-70200447614376411黑3114ii875i51916ff9173 0886 S929 6IS 4& 1660 10 si61 6B 84205381 ds 60 s1328&93 8483175140 151277 6 9 5* 亳551裁组规模为时a配且数据选择排序耗时分别为：S8 41 87 93 36 £ 62 32 90 5Ei- 05fi513432 322w

4、1594 9741 ?217a71寸 r- T- -寸寸寸寸寸寸寸. _ 一 一一 = 一 二- 一二-1 -<J_ J 二 dtLhrLt F - " - 1 - - - - - r “Itl =k =4 一-r -FanHH HHH!1图1、产生20组随机数组2、选择排序代码2:fori=0ton-2min=iforj=i+1ton-1交换元素ifelemin>elejmin=jswap(elei,elemin)/bzI"ersAdminitratorDesktop磔去年其1"；变财,"圈骰盘髓饕魄他s理蝌，型殷1数组规模ma*=1时,耗

5、时；M0B0000000Q0000O000B苣择排序平均耗时：噎秒数组规模=1醴时，耗时；QSO00000000000Q00OBQ选择排序平均耗时二曜秒数组规模倒*=10细时，耗时s22222322222222122322选择排序平均耗时：2.05毫秒数组规模MAX=10600时耗时；2041961941931941941961941941961951971951961?61951961941?2194选择排序平均耗时：仃525毫秒数组规模HRX=1眄眄团时,耗时才1975519887200961986219824199741966619S891989319841197511991219953

6、199381985719743197B419862198561982£选择排序平均耗时；取868.5毫秒图2、选择排序在不同数据规模下排序所消耗的时间3、冒泡排序代码3:fori=0ton-1forj=0ton-1-iifaj>aj+1swap(aj,aj+1)/交换"C:UsersAd ministratorXDes kto p般琼茸法“exc”11 回I.选择排序2.冒:建辨谱嘲融i序5,插入排序必退出程序强JPlEXM?EMiMMMWM：衰与施疑:M3<苴苴MK苴魏廉苴MM：M苴MMNMSMMMEX注XXM苴MXMM令MM%XXMJKMMMiOOt数组规模

7、MAX=10时.耗时：3»00«00«0000»00(10014胃泡排序平均耗时'H毫秒数组规模MAX=106时,耗时：00000000010000000010冒泡排序平均耗时工可，蠢秒数组规模MAX-10BH时.耗时：22221222222232222222冒泡排序平均耗时=2毫秒数组规模MAX=10000时.耗时11921981981921?21941?31961931?51941931?31?31931932B21941?31?2冒泡排序平均耗时：194.15毫秒数组规模MAX=100000时.耗时：19650197091973419660

8、19741197191974B1965819748197621982719682196531919G6719?t51977519tbH19G561970&冒泡排序平均耗时.陋毫秒图3、冒泡排序在不同数据规模下排序所消耗的时间3、合并排序代码4:MERGE(A,p,q,r)n1-q-p+1n2r-qcreatearraysL1n1+1andR1n2+1fori1ton1doLi-Ap+i-1forj1ton2doRj-Aq+jLn1+1-8Rn2+1ooi1j-1forkptordoifLi<RjthenAk-Lii-i+1elseAk-Rjj-j+1"T'C:U

9、5ersAd ministratorXDes ktop3W?, exe*|p 11 &|1.选择排序2.冒藕酚空需罐耳犍3序5.插入排序团退出程序珞次演演梵XXKM：KMM：美WEXXX苴苴苴KKM小兼多箕XKN苴苴MKM：就蜒共薜XXXM苴JKMKM：裁篝：M%XXMX整NM数组规模MAK=10时*耗时：合并排序平均耗时：齿毫秒数组规模MAX=106时,耗时：0000000000100010000合并排序平均耗时,g，毫秒数组规模MAX=1000时,耗时：11111100111111000101合并排序平均耗时：另门毫秒数组规模nflN-a0000时,耗时二666776EE6665E

10、E66666E合并排序平均耗时：6,始毫秒数组规模MAX=100000时,耗时；B26H5958506H605858585758G0596259G1625H5?合并排序平均耗时.“二毫秒.选择排序2.冒瀛照嚣翦怪厚犍导序5.插入排序机退出程序图4、合并排序在不同数据规模下排序所消耗的时间4、快速排序代码5:quick(ele0n-1,left,right)ifl<rlleftrrightxelel;whilel<rwhilel<r&&x<=eler比x小则之后交换到前面的部分r-ifl<relel-elerl+whilel<r&&am

11、p;x>elel比x大则前面交换到后面部分ll+ifl<reler-elelr-elelx;quick(ele,left,l-1)/递归调用quick(ele,l+1,right)图5、快速排序在不同数据规模下排序所消耗的时间5、插入排序代码6:fori=1-n-1ifelei<elei-1temp=eleiforj=i-1to0&&elej>tempelej+1elejelej+1temp图6、插入排序在不同数据规模下排序所消耗的时间三.实验分析选择排序：选择排序（ms）耗时(fTfi)图7、由图2数据整合而成的折线图表1、选择排序在不同数据规模下排序

12、所消耗的时间数据规模：10100100010000100000耗时（ms）002.05195.2519868.5图形上：形状基本符合n2（二次增长）数据上：我们发现当数据规模增大10倍时：100010000:195.25/2.05=95.2410010000100000:19868.5/195.25=101.75100其他倍数也可得到类似的结果。结论：当数据规模为10和100时因为数据太小，耗时约为0。但当数据规模为1000增大到10000时，并10000到100000时，规模增大10倍耗时都增大约100倍，可以计算出，选择排序的时间复杂度为o（n2）。冒泡排序:250002000015000

13、103005000冒泡排序耗时(ms)图8、由图3数据整合而成的折线图表2、冒泡排序在不同数据规模下排序所消耗的时间数据规模：10100100010000100000耗时(ms)00.12194.1519708图形上：形状基本符合n2(二次增长)数据上：我们发现当数据规模增大10倍时：1001000:2/0.1=20(误差太大)1000f10000:194.15/2=97.07510010000f100000:19708/194.15=101.5100其他倍数也可得到类似的结果。结论：由于开始问题规模较小，产生误差较大，但随着问题规模的按10的倍数增大，耗时逐渐呈100的倍数增大，分析伪代码也

14、可以算出该算法的时间复杂度为o(n2)。随着问题规模的增大，多种误差会逐渐累积，耗时会超过o(n2)的倍数，但是整体上不会相差太大。与此相比，电脑等其他因素造成轻微的误差可以忽略不计。合并排序：合并排序耗时（ms）图9、由图4数据整合而成的折线图表3、合并排序在不同数据规模下排序所消耗的时间数据规模：10100100010000100000耗时（ms）00.10.76.0559.2图形上：形状基本符合n（线性增长）数据上：我们发现当数据规模增大10倍时：1001000:0.7/0.1=7=10（误差较大）100010000:6.05/0.7=8.641010000100000:59.2/6.0

15、5=9.7810其他倍数也可得到类似的结果。结论：根据该算法的伪代码，可以计算出时间复杂度为o（nlog2n）,当数据规模扩大10倍时,耗时呈线性增长，逐渐接近于n。当数据规模扩大n倍时，相应的在时间的消耗上会扩大nlog2n倍，同时我们发现，理论上乘以nlog2n后的数据普遍会略小于实际数据，这主要原因快速排序需要递归调用，递归调用需要花费额外的时间。快速排序:快速排序(ms)150快速耗时(ms)图10、由图5数据整合而成的折线图表4、快速排序在不同数据规模下排序所消耗的时间数据规模：10100100010000100000耗时(ms)001.512.15137.95图形上：形状基本符合n

16、(线性增长)数据上：我们发现当数据规模增大10倍时：100010000:12.15/1.5=8.11010000100000:137.95/12.15=10.110其他倍数也可得到类似的结果。结论：根据快速排序算法的伪代码，可以分析出该算法的时间复杂度是o(nlog2n),当数据规模扩大n倍时，相应的在时间的消耗上会扩大nlog2n倍。从实验的数据上，可以看出随着问题规模的增大，耗时上面也呈线性增长，但累积起来的误差也使得程序的结果略微高于实验值。总体上的实验结果和预期还是很接近的。插入排序:12000插入排序100 DOsooo60004000200010000耗时(ms)1D0000图11

17、、由图6数据整合而成的折线图表5、插入排序在不同数据规模下排序所消耗的时间数据规模：10100100010000100000耗时(ms)001.2112.8511329.5图形上：形状基本符合n2(二次增长)数据上：我们发现当数据规模增大10倍时：100010000:112.85/1.2=94=10010000100000:11329.5/112.85=100.4=100其他倍数也可得到类似的结果。结论：根据插入算法的伪代码，可以计算出该算法的时间复杂度是o(n2),当数据规模扩大n倍时，相应的在时间的消耗上会扩大n2倍，理论上，如果数据大具有特殊性，那此算法被影响的程度会比较大，他的的比较次

18、数可以从线性次数，到n2次，赋值次数也可能由常数次变成n2总的来说，受数据影响较大。将五种排序的实验汇总在一起，如下图12所示五种排序250002000015000103005000选择耗时冒泡郴寸一台并耗时快速耗时量入搦寸图12、由图7、8、9、10、11整合而来从图中以及之前的分析中我们可以得到以下结论1、在平均时间复杂度上面，冒泡排序、插入排序和选择排序都最差为o(n2)。其主要原因是：随着问题规模的增大，冒泡排序在比较次数上达到了o(n2),但这种排序同时也受交换次数的影响，而且最多时间复杂度也是o(n2)。如此，同样是o(n2),但冒泡排序的二次项系数会比另外两个大不少，所以最为耗时

19、。2、快速排序和合并排序都表现出比较好的复杂度。但这两者中，合并排序表现更好。其原因是：在最坏情况下，即整个序列都已经有序且完全倒序的情况下，快速排序呈o(n2)的增长，而归并排序不管在什么情况下都呈o(nlogzn),随着问题规模的增大，快速排序逐渐体现出这种弊端。四.实验心得本次实验虽然花费很大的心思，但确实让我对这几种排序的认识更加深刻，同样的数据，排序的时间可以相差如此之大，这可能会改变我每次都使用冒泡排序的这一习惯，同时，对算法的优良性不同而导致的结果差异之大，感觉到好的算法是多么的重要，当然合理利用算法也是不可忽视的。这次实验虽然花了很大精力，却收获累累。指导教师批阅意见:成绩评定

20、:指导教师签字：年月日备注:注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。附录：代码#include<stdio.h>#include<iostream>#include<windows.h>#include<Mmsystem.h>usingnamespacestd;#include<ctime>#include<fstream>usingnamespacestd;#defineARRAY_MAX100000/*生成随机函数*/voidrand

21、Num(intMAX,int*array)srand(unsigned)time(NULL);/cout<<"生成的随机数为："<<endl;for(inti=0;i<MAX;i+)arrayi=rand()%100;/cout<<arrayi<<""/cout<<"tt耗时："/*选择排序*/voidselect_sort(intMAX,int*array)inti,j,k;for(i=0;i<MAX;i+)k=i;for(j=i+1;j<MAX;j+)i

22、f(arrayj<arrayk)k=j;if(k!=i)inttemp=arrayk;arrayk=arrayi;arrayi=temp;*I*voidbuddle_sort(intMAX,int*array)inti,j；for(i=0;i<MAX;i+)for(j=i+1;j<MAX;j+)if(arrayi>arrayj)swap(arrayi,arrayj);/*合并排序*/voidMerge(int*array,intp,intq,intr)intn1=q-p+1;intn2=r-q;int*L,*R,i,j,k;L=newintn1+1;R=newintn2

23、+1;for(i=0;i<n1;i+)Li=arrayp+i;for(i=0;i<n2;i+)Ri=arrayq+1+i;Ln1=INT_MAX;Rn2=INT_MAX;for(i=0,j=0,k=p;k<=r;k+)if(Li<=Rj)arrayk=Li+;elsearrayk=Rj+;deleteL;deleteR;voidmerge_sort(int*array,intp,intr)if(p<r)intq=(p+r)/2;merge_sort(array,p,q);/递归调用merge_sort(array,q+1,r);Merge(array,p,q,r)

24、;elsereturn;/*快速排序*/voidquick_sort(inta口，intlow,inthigh)if(low>=high)return;intfirst=low;intlast=high;intkey=afirst;while(first<last)while(first<last&&alast>=key)-last;afirst=alast;将比第一个小的数移到后面while(first<last&&afirst<=key)+first;alast=afirst;将比第一个大的数移到前面afirst=key;

25、/记录当前位置quick_sort(a,low,first-1);quick_sort(a,first+1,high);/*插入排序*/voidinsert_sort(intMAX,int*array)inti,j,temp;for(i=1;i<MAX;i+)temp=arrayi;for(j=i;j>0&&arrayj-1>temp;j-)arrayj=arrayj-1;arrayj=temp;intmain()intn,loop=1;while(loop!=0)产生随机数组clock_ttime_start,time_end;doubletime_used

26、=0,count=0;intMAX=10;intarrayARRAY_MAX;cout<<"ntt请输入序号选择相应的操作："<<endl;cout<<"1.选择排序2.冒泡排序3.合并排序4.快速排序5.插入排序0.退出程序"<<endl;cout<<"*"<<endl;cin>>n;switch(n)case0:loop=0;break;case 1:for(intj=0;j<5;j+)/控制问题规模MAX从10-100000cout<

27、<”数组规模MAX="<<MAX<<”时,耗时："<<endl;srand(unsigned)time(NULL);for(inti=0;i<20;i+)控制20组随机数产生randNum(MAX,array);time_start=clock();select_sort(MAX,array);time_end=clock();time_used=time_end-time_start;cout<<time_used<<""cout<<endl;count+=time_u

28、sed;cout<<"n选择排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count=0;MAX*=10;break;case 2:for(intj=0;j<5;j+)/控制问题规模MAX从10-100000cout<<”数组规模MAX="<<MAX<<”时,耗时："<<endl;srand(unsigned)time(NULL);for(inti=0;i<20;i+)控制20组随机数产生

29、randNum(MAX,array);time_start=clock();buddle_sort(MAX,array);time_end=clock();time_used=time_end-time_start;cout<<time_used<<""cout<<endl;count+=time_used;cout<<"n冒泡排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count=0;MAX*=10;brea

30、k;case 3:for(intj=0;j<5;j+)控制问题规模MAX从10-100000cout<<”数组规模MAX="<<MAX<<”时,耗时："<<endl;srand(unsigned)time(NULL);for(inti=0;i<20;i+)控制20组随机数产生randNum(MAX,array);time_start=clock();merge_sort(array,0,MAX-1);time_end=clock();time_used=time_end-time_start;cout<<time_used<<""cout<<endl;count+=time_used;cout<<"n合并排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count=0;MA