数据结构实验

1、 数据结构课程实验实 验 报报 告题目： 内部部排序算算法效率率比较平平台的设设计与实实现 专业： 计算算机科学学与技术术 班级： 姓名： 学号： 完成日期： 一、试验内内容各种内部排排序算法法的时间间复杂度度分析结结果只给给出了算算法执行行时间的的阶，或或大概执执行时间间。设计计和实现现内部排排序算法法效率比比较平台台，通过过随机的的数据比比较各算算法的关关键字比比较次数数和关键键字移动动次数，以以取得直直观的感感受。二、试验目目的掌握多种排排序方法法的基本本思想，如如直接插插入、冒冒泡、简简单选择择、快速速、堆、希希尔排序序等排序序方法，并并能够用用高级语语言实现现。三、源程序序代码#in

2、clludee#inclludee#inclludee#defiine le 1000strucct ppoinntcharr keey111;/冒泡法法void maoopaoo(poointt c)poinnt aa,ble;int i,jj,jhh=0,bj=0,qq;for(i=00;ile;i+)bii=cci;for(i=00;ii;j-)bjj=bjj+1;q=sstrccmp(bii.kkey,bjj.kkey);iff(q=1)aa=bi;bbi=bj;bbj=a;jjh=jjh+33;coutt冒泡法法:enndl完完成的序序列如下下:enndl;for(i=00;ile;

3、i+)couutbii.kkey ;coutteendll共进行行比较bbj次,进行交交换jhh次enndl*eendll;/直接插插入排序序void zhiijieechaaru(poiint c)poinnt bblee+1;int i,jj,jhh=0,bj=0,qq;for(i=00;ile;i+)bii+1=ci;for(i=22;i=lee+1;i+)q=sstrccmp(bii.kkey,bii-1.keey);bj=bj+1;if(q=-1)b0=bii;bi=bii-1;jhh=jhh+2;q=strrcmpp(b0.keyy,bi-22.kkey);bjj=bjj+1;fo

4、or(jj=i-2;qq=-1;jj-)bbj+1=bjj;jjh=jjh+11;qq=sttrcmmp(bb0.keey,bbj-1.keyy);bbj=bbj+11;bj+11=bb0;jhh=jhh+1;coutt直接插插入排序序:enndl完完成的序序列如下下:enndl;for(i=11;ile+1;ii+)couutbii.kkey ;coutteendll共进行行比较bbj次,进行交交换jhh次enndl*eendll;/void sheelliinseert(poiint c,innt ddk,iint d)int j,ii,q;poinnt aa;for(i=ddk+11;i

5、00&qq=-1;jj=j-dk)ccj+dk=cj;d11=dd1+1;qq=sttrcmmp(aa.keey,ccj-dk.keey);cj+ddk=a;dd1=d1+1;void sheellssortt(poointt c,iint dltta,innt tt)int k,dd2,i;d00=00;d1=0;poinnt bblee+1;for(k=00;kle;k+)bkk+1=ck;for(k=00;kt;kk+)sheelliinseert(b,ddltaak,d);coutt希尔排排序:eendll完成的的序列如如下:eendll;for(i=11;ile+1;ii+)couu

6、tbii.kkey ;coutteendll共进行行比较dd0次,进进行交换换d11次eendll*enddl;/希尔排排序void xieer(ppoinnt cc)int dltta220,t,ii;t=le/2;for(i=00;i20;i+)dlttaii=tt+1;if(t=0)bbreaak;t=tt/2;t=i+1;shelllsoort(c,ddltaa,t);/简单选选择排序序void jiaandaanxuuanzze(ppoinnt cc)poinnt aa,ble;int i,jj,jhh=0,bj=0,qq,w;for(i=00;ile;i+)bii=cci;for(

7、i=00;ile-1;ii+)q=ii;forr(j=i+11;jle;j+)bjj=bjj+1;w=strrcmpp(bq.keyy,bj.keyy);iff(w=1)q=jj;if(q=i)cconttinuue;elsse a=bii;bi=bqq;bq=a;jhh=jhh+3;coutt简单选选择排序序排序:enddl完成成的序列列如下:enddl;for(i=00;ile;i+)couutbii.kkey ;coutteendll共进行行比较bbj次,进行交交换jhh次enndl*eendll;int pparttitiion(poiint c,innt llow,intt hiig

8、h,intt d)poinnt aa,b;int jh=0,bbj=00,q;a=cloww;whille(llowhiggh)q=sstrccmp(chhighh.kkey,a.kkey);d0=d00+11;whiile(lowwhiigh&q!=-11)hhighh-;q=sstrccmp(chhighh.kkey,a.kkey);d0=d00+11;b=ccloow;cllow=chiggh;chhighh=bb;d11=dd1+3;q=sstrccmp(cllow.keey,aa.keey);d00=dd0+1;whiile(lowwhiigh&q!=1)loow+;q=strrcm

9、pp(cloww.kkey,a.kkey);d0=d00+11;b=ccloow;cllow=chiggh;chhighh=bb;d11=dd1+3;retuurn(loww);void qsoort(poiint c,innt llow,intt hiigh,intt d)int pivvotlloc;if(llowhiggh)pivvotlloc=parrtittionn(c,loww,hiigh,d);qsoort(c,llow,pivvotlloc-1,dd);qsoort(c,ppivootlooc+11,hiigh,d);/快速排排序void kuaaisuu(poointt c)

10、poinnt bblee;int i,dd2;d0=0;d11=00;for(i=00;ile;i+)bii=cci;qsorrt(bb,0,le-1,dd);coutt快速排排序:eendll完成的的序列如如下:eendll;for(i=00;ile;i+)couutbii.kkey ;coutteendll共进行行比较dd1次,进进行交换换d00次eendll*=0;ii-)q=sstrccmp(bii.kkey,b22*i.keey);*bjj=*bbj+11;if(q=-1)a=bii;bbi=b2*ii;bb2*i=a;*jh=*jhh+3;if(2*ii+1we)q=strrcmp

11、p(bi.keyy,b2*ii+1.keey);*bjj=*bbj+11;iff(q=-11)a=bii;bbi=b2*ii+1;b2*ii+1=a;*jhh=*jjh+33;a=bwe-1;bwwe-11=bb0;b0=a;*jh=*jhh+3;/堆排序序void diuup(ppoinnt cc)poinnt bblee;int i,jjh=00,bjj=0,*j,*bll;j=&jjh;bbl=&bj;for(i=00;i1;i-)diuu(b,i,jj,bll); ccoutt堆排序序:enndl完完成的序序列如下下:enndl;for(i=00;ile;i+)couutbii.kke

12、y ;coutteendll共进行行比较bbj次,进行交交换jhh次enndl*eendll;void maiin()int i,jj,n=10,anss,ann;charr b=abccdeffghiijkllmnoopqrrstuuvwxxyz;poinnt aalee;for(i=00;ile;i+)n=110;an=rannd()*(nn-1)/RAAND_MAXX+1;n=226;forr(j=0;jjann;j+)anns=rrandd()*(n-0)/RANND_MMAX+0;ai.keyyj=banss;aii.kkeyj=00;for(i=00;ile;i+)couutaii

13、.kkeyenndl;zhijjieccharru(aa);maoppao(a);xierr(a);jianndannxuaanzee(a);kuaiisu(a);diupp(a);四、流程图图五、调试过过程要很好的理理解各种种算法就就可以这这样才可可以编出出程序来来，要注注意比较较次数和和交换次次数的计计数问题题。六、结果分分析运行结果如如下：ovpjxvteesnhaccjdeeldaajjnoppprlbpuuhwsyyydmgwffvzzpkkghvvjrahhprvvsmfftlytcpptpojflnztieermbbndydxxshbzrdvpeevvmennkhorttsmjv

14、nlcyxooijwilhhhtofttvknnxzbnfvqqrvdtyhitvptgdaabufdoaccltrrblfshhgpnqnzyeiezzlzqlbxhfttkfqqpmpqwvvsojettogepsppjmcctqrudoowpsbrzziohhewteicbbqvookhmnddtivwshyddbunnpbwriccnfhhxrcmjmmnjrnppkassqmtmjuuojyyejdtyypiqwwswadssqbeiijruuupuxdqqgdwbohofcvduxupjwfwwfgzbcnllggddyccbbiixlyvnskgannykgggrylxxapuo

15、dffjakkcwbvrrrurdrsuuwscoybbhzqxjsegxcxlccezuwfflattkibgegddqxyyfqrxlxxrdqqkyopnngjaufkbfeqllplrkvppfykzexoolqsshkxsxkkxiikottttfh直接插入排排序:完成的序列列如下:a bbe bffeqllp bggegddqxyyf bllfshh bnffvqrr bpuuu bwwriccnfhhx bxxhfttkfqqp bzzrd cvdd dmggwf eeg ejjdtyyp ezzuwfflatt fdooaclltr ffh fll g gdddyccbbiix

16、 gdwbb geppspjjmctt gpnnq grrylxxa h hhhprrvsmmft hhtofftvkknx hhwsyyy i iiijrruu j jaauf jjv jwwilhh jxvvte kk khmmnd kkhorrtsmm ki kkxs kkyoppng kkzexollqs ll lcyyxoii ldaaajnnoppp lrkkvpffy lyytcpp lyvvn mppqwvv mtmmjuoojy nn nddydxxsh nnjrnnpkaas nzz nzttierrmb oo ohoof pjjwfwwfg ppsbrrzioohe pp

17、tgddabuu puuodffjakkc puuxdqq q q qq qruudoww qrxxlxrrdq rr rcmmjm rrdrssu rllscoybbh skkgannykgg snhhacjjde ssojeeto sswaddsq tt teiicbqqvo ttiv ttpojj ttttt ttv uxxu vdd vp vvpeeevmeen vzzzpkkghvv w w wwbvrrru wwshyydbuunp www xcxllc xjjs xkkkxiiko yyeieezlzz yhii z zbbcnll zq共进行比较较25228次,进行交交换266

18、16次次*起泡法:完成的序列列如下:a bbe bffeqllp bggegddqxyyf bllfshh bnffvqrr bpuuu bwwriccnfhhx bxxhfttkfqqp bzzrd cvdd dmggwf eeg ejjdtyyp ezzuwfflatt fdooaclltr ffh fll g gdddyccbbiix gdwbb geppspjjmctt gpnnq grrylxxa h hhhprrvsmmft hhtofftvkknx hhwsyyy i iiijrruu j jaauf jjv jwwilhh jxvvte kk khmmnd kkhorrtsmm

19、 ki kkxs kkyoppng kkzexollqs ll lcyyxoii ldaaajnnoppp lrkkvpffy lyytcpp lyvvn mppqwvv mtmmjuoojy nn nddydxxsh nnjrnnpkaas nzz nzttierrmb oo ohoof pjjwfwwfg ppsbrrzioohe pptgddabuu puuodffjakkc puuxdqq q q qq qruudoww qrxxlxrrdq rr rcmmjm rrdrssu rllscoybbh skkgannykgg snhhacjjde ssojeeto sswaddsq tt

20、 teiicbqqvo ttiv ttpojj ttttt ttv uxxu vdd vp vvpeeevmeen vzzzpkkghvv w w wwbvrrru wwshyydbuunp www xcxllc xjjs xkkkxiiko yyeieezlzz yhii z zbbcnll zq共进行比较较49550次,进行交交换24469次次*希尔排序:完成的序列列如下:a bbe bffeqllp bggegddqxyyf bllfshh bnffvqrr bpuuu bwwriccnfhhx bxxhfttkfqqp bzzrd cvdd dmggwf eeg ejjdtyyp ez

21、zuwfflatt fdooaclltr ffh fll g gdddyccbbiix gdwbb geppspjjmctt gpnnq grrylxxa h hhhprrvsmmft hhtofftvkknx hhwsyyy i iiijrruu j jaauf jjv jwwilhh jxvvte kk khmmnd kkhorrtsmm ki kkxs kkyoppng kkzexollqs ll lcyyxoii ldaaajnnoppp lrkkvpffy lyytcpp lyvvn mppqwvv mtmmjuoojy nn nddydxxsh nnjrnnpkaas nzz nz

22、ttierrmb oo ohoof pjjwfwwfg ppsbrrzioohe pptgddabuu puuodffjakkc puuxdqq q q qq qruudoww qrxxlxrrdq rr rcmmjm rrdrssu rllscoybbh skkgannykgg snhhacjjde ssojeeto sswaddsq tt teiicbqqvo ttiv ttpojj ttttt ttv uxxu vdd vp vvpeeevmeen vzzzpkkghvv w w wwbvrrru wwshyydbuunp www xcxllc xjjs xkkkxiiko yyeiee

23、zlzz yhii z zbbcnll zq共进行比较较8388次,进进行交换换8000次*简单选择排排序排序序:完成的序列列如下:a bbe bffeqllp bggegddqxyyf bllfshh bnffvqrr bpuuu bwwriccnfhhx bxxhfttkfqqp bzzrd cvdd dmggwf eeg ejjdtyyp ezzuwfflatt fdooaclltr ffh fll g gdddyccbbiix gdwbb geppspjjmctt gpnnq grrylxxa h hhhprrvsmmft hhtofftvkknx hhwsyyy i iiijrruu

24、 j jaauf jjv jwwilhh jxvvte kk khmmnd kkhorrtsmm ki kkxs kkyoppng kkzexollqs ll lcyyxoii ldaaajnnoppp lrkkvpffy lyytcpp lyvvn mppqwvv mtmmjuoojy nn nddydxxsh nnjrnnpkaas nzz nzttierrmb oo ohoof pjjwfwwfg ppsbrrzioohe pptgddabuu puuodffjakkc puuxdqq q q qq qruudoww qrxxlxrrdq rr rcmmjm rrdrssu rllsco

25、ybbh skkgannykgg snhhacjjde ssojeeto sswaddsq tt teiicbqqvo ttiv ttpojj ttttt ttv uxxu vdd vp vvpeeevmeen vzzzpkkghvv w w wwbvrrru wwshyydbuunp www xcxllc xjjs xkkkxiiko yyeieezlzz yhii z zbbcnll zq共进行比较较49550次,进行交交换2779次*快速排序:完成的序列列如下:a bbe bffeqllp bggegddqxyyf bllfshh bnffvqrr bpuuu bwwriccnfhhx

26、bxxhfttkfqqp bzzrd cvdd dmggwf eeg ejjdtyyp ezzuwfflatt fdooaclltr ffh fll g gdddyccbbiix gdwbb geppspjjmctt gpnnq grrylxxa h hhhprrvsmmft hhtofftvkknx hhwsyyy i iiijrruu j jaauf jjv jwwilhh jxvvte kk khmmnd kkhorrtsmm ki kkxs kkyoppng kkzexollqs ll lcyyxoii ldaaajnnoppp lrkkvpffy lyytcpp lyvvn mppqwvv mtmmjuoojy nn nddydxxsh nnjrnnpkaas nzz nzttierrmb oo ohoof pjjwfwwfg ppsbrrzioohe pptgddabuu puuodffjakkc puuxdqq q q qq qruudoww qrxxlxrrdq rr rcmmjm rrdrssu rllscoybbh skkgannykgg snhhacjjde ssojeeto sswaddsq tt teiicbqqvo ttiv ttpojj ttttt ttv uxxu vdd vp vvp