數(shù)據(jù)結(jié)構(gòu)實驗

1、 數(shù)據(jù)結(jié)構(gòu)課程實驗實 驗 報報 告題目： 內(nèi)部部排序算算法效率率比較平平臺的設(shè)設(shè)計與實實現(xiàn) 專業(yè)： 計算算機科學學與技術(shù)術(shù) 班級： 姓名： 學號： 完成日期： 一、試驗內(nèi)內(nèi)容各種內(nèi)部排排序算法法的時間間復雜度度分析結(jié)結(jié)果只給給出了算算法執(zhí)行行時間的的階，或或大概執(zhí)執(zhí)行時間間。設(shè)計計和實現(xiàn)現(xiàn)內(nèi)部排排序算法法效率比比較平臺臺，通過過隨機的的數(shù)據(jù)比比較各算算法的關(guān)關(guān)鍵字比比較次數(shù)數(shù)和關(guān)鍵鍵字移動動次數(shù)，以以取得直直觀的感感受。二、試驗目目的掌握多種排排序方法法的基本本思想，如如直接插插入、冒冒泡、簡簡單選擇擇、快速速、堆、希希爾排序序等排序序方法，并并能夠用用高級語語言實現(xiàn)現(xiàn)。三、源程序序代碼#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);四、流程圖圖五、調(diào)試過過程要很好的理理解各種種算法就就可以這這樣才可可以編出出程序來來，要注注意比較較次數(shù)和和交換次次數(shù)的計計數(shù)問題題。六、結(jié)果分分析運行結(jié)果如如下：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