排序算法的比較與實(shí)現(xiàn)

1、雜難W磐云南大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（本實(shí)驗(yàn)項(xiàng)目方案受“教育部人才培養(yǎng)模式創(chuàng)新實(shí)驗(yàn)區(qū)（X3108005）”項(xiàng)目資助）實(shí)驗(yàn)難度：ABC序號(hào)學(xué)號(hào)姓名成績(jī)指導(dǎo)教師（簽名）學(xué)期：2014秋季學(xué)期任課教師：張德海王常吉實(shí)驗(yàn)題目:排序算法的比較與實(shí)現(xiàn)小組長(zhǎng)：聯(lián)系電話:電子郵件：完成提交時(shí)間：2015年1月4日云南大學(xué)軟件學(xué)院2014學(xué)年秋季學(xué)期數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)成績(jī)考核表、【實(shí)驗(yàn)構(gòu)思(Conceive)】(10%)(本部分應(yīng)包括：描述實(shí)驗(yàn)實(shí)現(xiàn)的基本思路，包括所用到的離散數(shù)學(xué)、工程數(shù)學(xué)、程序設(shè)計(jì)、算法等相關(guān)知識(shí))統(tǒng)計(jì)六種排序方法的關(guān)鍵詞比較次數(shù)和記錄移動(dòng)次數(shù)，首先用偽隨機(jī)數(shù)的方式產(chǎn)生隨機(jī)數(shù)據(jù)，然后按用戶選擇分

2、別調(diào)用六種排序方式的函數(shù)，在子函數(shù)中可使用兩個(gè)計(jì)數(shù)變量記錄比較次數(shù)和移動(dòng)次數(shù)。由于要求統(tǒng)計(jì)完全正序、完全逆序和無(wú)序等不同情況下的結(jié)果，所以在生成隨機(jī)數(shù)據(jù)時(shí)應(yīng)讓用戶選擇隨機(jī)數(shù)據(jù)類型，若是有序，可在使用前先調(diào)用任意排序函數(shù)，達(dá)到數(shù)據(jù)有序的目的。二、【實(shí)驗(yàn)設(shè)計(jì)(Design)】(20%)(本部分應(yīng)包括：抽象數(shù)據(jù)類型的功能規(guī)格說(shuō)明、主程序模塊、各子程序模塊的偽碼說(shuō)明，主程序模塊與各子程序模塊間的調(diào)用關(guān)系)選用兩個(gè)數(shù)組存儲(chǔ)數(shù)據(jù)，通過(guò)數(shù)組地址和元素個(gè)數(shù)作為參數(shù)調(diào)用函數(shù)。由于在一次排序后，該數(shù)組元素已為正序排列，為了程序可連續(xù)運(yùn)行，利用開始時(shí)便復(fù)制好的數(shù)組進(jìn)行賦值操作，回復(fù)到初始數(shù)據(jù)狀態(tài)，以便于同其他排序方

3、式進(jìn)行比較。在每次排序函數(shù)調(diào)用前都將計(jì)數(shù)變量清零，以免操作時(shí)出現(xiàn)不可預(yù)知的錯(cuò)誤。三、【實(shí)現(xiàn)描述(Implement)】(30%)(本部分應(yīng)包括：抽象數(shù)據(jù)類型具體實(shí)現(xiàn)的函數(shù)原型說(shuō)明、關(guān)鍵操作實(shí)現(xiàn)的偽碼算法、函數(shù)設(shè)計(jì)、函數(shù)間的調(diào)用關(guān)系，關(guān)鍵的程序流程圖等，給出關(guān)鍵算法的時(shí)間復(fù)雜度分析。)測(cè)試數(shù)據(jù)的產(chǎn)生：首先由用戶輸入記錄的個(gè)數(shù)，無(wú)序的數(shù)據(jù)由隨機(jī)數(shù)產(chǎn)生器生成。正序和逆序的數(shù)記錄在list中。隨機(jī)數(shù)產(chǎn)生代碼：srand(unsigned)time(NULL);for(inti=1;il+1;i+)listi.SetKey(rand()%1000);排序及記錄比較和移動(dòng)次數(shù)的過(guò)程：冒泡排序：voidBu

4、bble(Element*list,intn)記錄移動(dòng)和比較次數(shù)的變量：intcountbm=0,countbc=0;相鄰兩個(gè)元素每比較一次，countbm加1，若前面的數(shù)比后面的數(shù)大，則需要兩數(shù)進(jìn)行交換。每交換一次countbm加3.直接插入排序：voidInsertSort(Element*list,intn)記錄移動(dòng)和比較次數(shù)的變量：intcountim=0,countic=0;待排序文件中無(wú)序部分的元素每和有序部分元素比較一次，記錄比較次數(shù)的變量countim加1，無(wú)序部分即將排好序元素在和有序部分的元素進(jìn)行比較時(shí)，將此元素記錄在臨時(shí)變量e中，此時(shí)countim加1，將每一比此元素小的

5、已排好序的元素以此后移，每后移一次，countim加1，再將e放入合適位置，此時(shí)countim加1.簡(jiǎn)單選擇排序：voidSSort(Element*list,intn)記錄移動(dòng)和比較次數(shù)的變量：intcountsm=0,countsc=0;每次選出待排序文件中最小的元素，在選擇過(guò)程中，元素每比較一次countsc加1，將最小的元素與未排序部分的第一個(gè)元素進(jìn)行交換，每交換一次countsm加3，這也是元素個(gè)數(shù)相同的文件排序完成后移動(dòng)次數(shù)和比較次數(shù)不變的原因?？焖倥判颍簐oidqsort(Element*list,intn)記錄移動(dòng)和比較次數(shù)的變量：intcountqm=0,countqc=0;

6、這個(gè)函數(shù)調(diào)用了遞歸函數(shù)voidQSort(Element*list,intm,intn)，因此，變量countqm,countqc定義為全局變量，在遞歸函數(shù)中，首先定義一個(gè)標(biāo)志元素，在此函數(shù)中選用的每個(gè)分劃文件的第一個(gè)元素，標(biāo)志元素和從文件開頭的元素從前往后比較，直到有比標(biāo)志元素大的元素，標(biāo)志元素再和文件結(jié)尾的元素從后往前比較，直到有比標(biāo)志元素小的元素，每比較一次countqc加1，此時(shí)將大元素和小元素交換，countqm加3.將文件分成了以標(biāo)志元素為界限的兩個(gè)文件，再將標(biāo)志元素放在兩個(gè)元素中間的位置，此時(shí)countqm加3.再對(duì)兩個(gè)文件分別進(jìn)行快速排序。希爾排序：voidShellSort(

7、Element*list,intn)記錄移動(dòng)和比較次數(shù)的變量：intcountlm=0,countlc=0希爾排序是將文件分組，然后進(jìn)行插入排序，因此countlm,countlc的增量方式與直接插入排序相同。堆排序：voidHeapSort(Element*list,constintn)記錄移動(dòng)和比較次數(shù)的變量：intcountrm=0,countrc=0首先進(jìn)行初始建堆voidRestore(Element*tree,constintroot,constintn)，將待排序文件保存在完全二叉樹中，從最后一個(gè)非葉節(jié)點(diǎn)開始，將其孩子結(jié)點(diǎn)與其進(jìn)行比較，每比較一次countrc加1，若孩子結(jié)點(diǎn)比其

8、大，二者交換countrm加3，直到任意結(jié)點(diǎn)的關(guān)鍵詞大于等于它的兩個(gè)孩子結(jié)點(diǎn)。在進(jìn)行堆排序，將根節(jié)點(diǎn)與最后一個(gè)葉節(jié)點(diǎn)交換，countrm加3，再進(jìn)行初始建堆，直至完全排好序。四、【測(cè)試結(jié)果(Testing)】(10%)(本部分應(yīng)包括：對(duì)實(shí)驗(yàn)的測(cè)試結(jié)果，應(yīng)具體列出每次測(cè)試所輸入的數(shù)據(jù)以及輸出的數(shù)據(jù)，并對(duì)測(cè)試結(jié)果進(jìn)行分析總結(jié))待排序文件排序方式冒泡排序直接插入排序簡(jiǎn)單選擇排序快速排序希爾排序堆排序亂序1比較次數(shù)49297024607249950012782148303820移動(dòng)次數(shù)73521924707129977296228364233亂序2比較次數(shù)49623825521149950012927

9、148683788移動(dòng)次數(shù)76263625621029977449228744185亂序3比較次數(shù)49757824298949950012951148453818移動(dòng)次數(shù)72597024398829977335228514230亂序4比較次數(shù)49674924839949950012644151543784移動(dòng)次數(shù)74220024939829977353231604179亂序5比較次數(shù)49435424611949950013766162293834移動(dòng)次數(shù)73536024711829977326242354254正序比較次數(shù)99999949950050250080064996移動(dòng)次數(shù)019982

10、9973000160125997逆序比較次數(shù)499500500499499500502503127153000移動(dòng)次數(shù)149850050149829973000207213003四、【實(shí)驗(yàn)總結(jié)】（10%）（本部分應(yīng)包括：自己在實(shí)驗(yàn)中完成的任務(wù)，注意組內(nèi)的任意一位同學(xué)都必須獨(dú)立完成至少一項(xiàng)接口的實(shí)現(xiàn)；對(duì)所完成實(shí)驗(yàn)的經(jīng)驗(yàn)總結(jié)、心得）從這次的實(shí)驗(yàn)中，我看到了自己的不足，首先就是比較輕浮，不能夠踏踏實(shí)實(shí)的，其次，就是我個(gè)人的動(dòng)手操作能力，即上機(jī)編程能力還是十分欠缺的，這還是我們平時(shí)鍛煉的少所造成的。所以在以后的學(xué)習(xí)中我們要加強(qiáng)這方面的鍛煉。五、【項(xiàng)目運(yùn)作描述（Operate）（10%）（本部分應(yīng)包括：

11、項(xiàng)目的成本效益分析，應(yīng)用效果等的分析。）本程序可以實(shí)現(xiàn)基本的學(xué)生查找排序功能，可以根據(jù)程序所產(chǎn)生的隨機(jī)數(shù)來(lái)進(jìn)行查找。因?yàn)楸境绦虿⒉痪邆淇梢暬倪\(yùn)行界面，因此本程序并不具備較高的成本價(jià)值，但同時(shí)也因?yàn)楸境绦蛑谱鞒杀静⒉桓?，因此其效益相?duì)來(lái)說(shuō)尚可。六、【代碼（10%）（本部分應(yīng)包括：完整的代碼及充分的注釋。注意紙質(zhì)的實(shí)驗(yàn)報(bào)告無(wú)需包括此部分。格式統(tǒng)一為，字體:Georgia,行距:固定行距12，字號(hào):小五）#include#includeusingnamespacestd;intcountqm=o,countqc=o;快排移動(dòng)和比較intcountrm=o,countrc=o;堆排序移動(dòng)和比較cla

12、ssElementprivate:intkey;/待排序記錄中個(gè)關(guān)鍵字public:intGetKey()constreturnkey;voidSetKey(intk)key=k;/輸出排序后的文件voidoutput(Element*list,intn)for(inti=1;i=n;i+)coutlisti.GetKey();/氣泡排序voidBubble(Element*list,intn)intbound,j,t;intcountbm=o,countbc=o;移動(dòng)次數(shù)、比較次數(shù)Elemente;bound=n;while(bound)t=o;for(j=1;jlistj+1.GetKey

13、()e=listj;countbm+;listj=listj+1;countbm+;listj+1=e;countbm+;t=j;bound=t;countbmendl;cout冒泡排序比較次數(shù)：countbc冒泡排序移動(dòng)次數(shù):/直接插入排序voidInsertSort(Element*list,intn)intcountim=o,countic=o;Elemente;listo.SetKey(-1);for(intj=2;j=n;j+)e=listj;countim+;inti=j-1;countic+;while(e.GetKey()listi.GetKey()countic+;listi

14、+1=listi;countim+;i-;listi+1=e;countim+;cout插入排序比較次數(shù)：countic插入排序移動(dòng)次數(shù)：countim=2;j-)t=1;for(inti=2;i=j;i+)countsc+;if(listt.GetKey()listi.GetKey()t=i;e=listt;countsm+;listt=listj;countsm+;listj=e;countsm+;countsmendl;cout選擇排序比較次數(shù)：countsc選擇排序移動(dòng)次數(shù):/快速排序voidQSort(Element*list,intm,intn)inti,j,k,temp;if(m

15、n)i=m;j=n+1;k=listm.GetKey();while(ij)i+;countqc+;while(listi.GetKey()k)countqc+;j-;if(ij)temp=listi.GetKey();countqm+;listi.SetKey(listj.GetKey();countqm+;listj.SetKey(temp);countqm+;temp=listm.GetKey();countqm+;listm.SetKey(listj.GetKey();countqm+;listj.SetKey(temp);countqm+;QSort(list,m,j-1);QSor

16、t(list,j+1,n);/快速排序的輸出voidqsort(Element*list,intn)/intcountqm=o,countqc=o;快排移動(dòng)和比較countqmendl;QSort(list,0,n);cout快速排序比較次數(shù)：countqc=1)gap=gap/2;for(i=1;i=gap;i+)Elemente;intt;for(intj=i+gap;j=n;j=j+gap)e=listj;countlm+;t=j-gap;countlc+;while(e.GetKey()listt.GetKey()countlc+;listt+gap=listt;countlm+;t=

17、t-gap;if(t=i)break;listt+gap=e;countlm+;cout希爾排序比較次數(shù)：countlc希爾排序移動(dòng)次數(shù)：countlmendl;/堆排序_初始建堆voidRestore(Element*tree,constintroot,constintn)/intcountrm=0,countrc=0;intm,temp;intj=root;while(j=(int)(n/2)countrc+;if(2*jn)&(tree2*j.GetKey()tree2*j+1.GetKey()m=2*j+1;elsem=2*j;countrc+;if(treej.GetKey()=1;

18、i-)Restore(list,i,n);for(i=n;i1;i-)temp=list1.GetKey();countrm+;list1.SetKey(listi.GetKey();countrm+;listi.SetKey(temp);countrm+;Restore(list,1,i-1);cout堆排序比較次數(shù)：countrc堆排序移動(dòng)次數(shù)：countrmendl;countrm=0,countrc=0;/主函數(shù)intmain()intl,m;cout排序算法的比較endl;cout請(qǐng)輸入待排序文件中關(guān)鍵字的個(gè)數(shù)l;coutm;coutendl;Element*list=newElem

19、entl+1;srand(unsigned)time(NULL);coutendl;for(inti=1;im+1;i+)for(inti=1;il+1;i+)cout*第i次比較listi.SetKey(rand()%1000);/冒泡排序Element*listb=newElementl+1;for(i=1;il+1;i+)listbi.SetKey(listi.GetKey();cout冒泡排序endl;Bubble(listb,l);/直接插入排序Element*listi=newElementl+1;for(i=1;il+1;i+)listii.SetKey(listi.GetKey

20、();cout直接插入排序endl;InsertSort(listi,l);/選擇排序Element*lists=newElementl+1;for(i=1;il+1;i+)listsi.SetKey(listi.GetKey();cout選擇排序endl;SSort(lists,l);/快速排序Element*listq=newElementl+1;for(i=1;il+1;i+)listqi.SetKey(listi.GetKey();cout快速排序endl;qsort(listq,l);/希爾排序Element*listl=newElementl+1;for(i=1;il+1;i+)l

21、istli.SetKey(listi.GetKey();cout希爾排序endl;ShellSort(listl,l);/堆排序Element*listh=newElementl+1;for(i=1;il+1;i+)listhi.SetKey(listi.GetKey();cout堆排序endl;HeapSort(listh,l);/output(listh,l);cout正序*比較次數(shù):endl;/創(chuàng)建正序文件for(i=1;il+1;i+)listi.SetKey(i);/coutlisti.GetKey();/冒泡排序cout冒泡排序endl;Bubble(list,l);/直接插入排序cout直接插入排序endl;InsertSort(list,l);/選擇排序cout選擇排序endl;SSort(list,l);/快速排序cout快速排序endl;qsort(list,l);/output(list,l);/希爾