版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p><b> 課程設(shè)計(jì)(論文)</b></p><p> 題 目 名 稱 幾種常見(jiàn)的排序算法的實(shí)現(xiàn)與性能分析 </p><p> 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p> 學(xué) 生 姓 名 </p>
2、;<p> 學(xué) 號(hào) </p><p> 系 、專 業(yè) 信息工程系、通信工程 </p><p> 指 導(dǎo) 教 師 </p><p> 2012年 12 月 23 日&
3、lt;/p><p><b> 摘 要</b></p><p> 設(shè)計(jì)一個(gè)測(cè)試程序比較起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)。運(yùn)用多種自定義函數(shù),通過(guò)在主函數(shù)中調(diào)用自定義函數(shù),實(shí)現(xiàn)其功能,最后輸出相應(yīng)算法的比較次數(shù)(至少有五種不同的數(shù)據(jù))和移動(dòng)次數(shù)(關(guān)鍵字的交換記為三次移動(dòng))。從而直觀的判斷各內(nèi)部排序算法性能的優(yōu)劣性
4、。</p><p> 關(guān)鍵詞:起泡排序;直接排序;簡(jiǎn)單選擇排序;快速排序;希爾排序;堆排序;內(nèi)部排序;直觀;比較次數(shù);移動(dòng)次數(shù)</p><p><b> 目錄</b></p><p><b> 1 問(wèn)題描述1</b></p><p><b> 2 需求分析1</b>
5、</p><p><b> 3 概要設(shè)計(jì)1</b></p><p> 3.1抽象數(shù)據(jù)類型定義1</p><p><b> 3.2模塊劃分2</b></p><p><b> 4 詳細(xì)設(shè)計(jì)3</b></p><p> 4.1數(shù)據(jù)類型的定義
6、3</p><p> 4.2主要模塊的算法描述3</p><p><b> 5 測(cè)試分析8</b></p><p> 6 課程設(shè)計(jì)總結(jié)12</p><p><b> 參考文獻(xiàn)12</b></p><p> 附錄(源程序清單)13</p>&
7、lt;p><b> 1 問(wèn)題描述</b></p><p> 設(shè)計(jì)一個(gè)測(cè)試程序比較起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法的關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)以取得直觀感受。待排序表的表長(zhǎng)不小于100,表中數(shù)據(jù)隨機(jī)產(chǎn)生,至少用5組不同數(shù)據(jù)作比較,比較指標(biāo)有:關(guān)鍵字參加比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換記為3次移動(dòng))。最后輸出比較結(jié)果。</p><
8、p><b> 2 需求分析</b></p><p> ?。?)用數(shù)組S來(lái)存放系統(tǒng)隨機(jī)產(chǎn)生的100個(gè)數(shù)據(jù),并放到R數(shù)組中,數(shù)據(jù)由程序隨機(jī)產(chǎn)生,用戶只需查看結(jié)果。</p><p> (2)利用全局變量times和changes來(lái)分別統(tǒng)計(jì)起泡排序、直接排序、簡(jiǎn)單選擇排序、快速排序、希爾排序、堆排序算法的比較次數(shù)和移動(dòng)次數(shù),然后輸出結(jié)果,并在每一次統(tǒng)計(jì)之后,將tim
9、es和changes都賦值為0。</p><p> (3)在主函數(shù)中調(diào)用用戶自定義函數(shù),輸出比較結(jié)果。</p><p> ?。?)本程序是對(duì)幾種內(nèi)部排序算法的關(guān)鍵字進(jìn)行性能分析的程序,它分為以下幾個(gè)部分:a、建立數(shù)組;b、調(diào)用函數(shù)求比較和移動(dòng)次數(shù);c、輸出結(jié)果。</p><p><b> 3 概要設(shè)計(jì)</b></p><
10、p> 3.1抽象數(shù)據(jù)類型定義</p><p><b> 排序數(shù)據(jù)類型定義:</b></p><p> ADT paixu{</p><p> 數(shù)據(jù)對(duì)象:D={aij|aij屬于{1,2,3…},i,j>0}</p><p> 數(shù)據(jù)關(guān)系:R={<ai-1,ai>|ai-1,ai∈D,i=2
11、,...,n}</p><p><b> 基本操作:</b></p><p> Insertsort();</p><p> 初始條件:數(shù)組已經(jīng)存在。</p><p> 基本思想:將一個(gè)記錄插入到已經(jīng)排好序的有序列表中,從而得到了一個(gè)新的、記錄新增1的有序表。 </p><p> She
12、llsort();</p><p> 初始條件:數(shù)組已經(jīng)存在。</p><p> 基本思想:先取定一個(gè)正整數(shù)d1<n,把全部記錄分成d1個(gè)組,所有距離為d1倍數(shù)的記錄放在一組中,在各組內(nèi)進(jìn)行插入排序,然后取d2<d1重復(fù)上述分組和排序工作,直至取di=1,即所有記錄放在一個(gè)組中排序?yàn)橹埂?lt;/p><p> Bubblesort();</p&g
13、t;<p> 初始條件:數(shù)組已經(jīng)存在。</p><p> 基本思想:兩兩比較待排序記錄的鍵值,并交換不滿足順序要求的那些偶對(duì),直到全部滿足順序要求為止。</p><p> QuickSort(int low,int high);</p><p> 初始條件:數(shù)組已經(jīng)存在。</p><p> 基本思想:在待排序的n個(gè)記錄
14、中任取一個(gè)記錄(通常取第一個(gè)記錄),以該記錄的鍵值為基準(zhǔn)用交換的方法將所有記錄分成兩部分,所有鍵值比它小的安置在一部分,所有鍵值比它大的安置在另一部分,并把該記錄排在兩部分的中間,也就是該記錄的最終位置。這個(gè)過(guò)程稱為一趟快速排序。然后分別對(duì)所劃分的兩部分重復(fù)上述過(guò)程,一直重復(fù)到每部分內(nèi)只有一個(gè)記錄為止排序完成。</p><p> Selectsort();</p><p> 初始條件:
15、數(shù)組已經(jīng)存在。</p><p> 基本思想:每次從待排序的記錄中選出鍵值最?。ɑ蜃畲螅┑挠涗洠樞蚍旁谝雅判虻挠涗浶蛄械淖詈?,直到全部排完。對(duì)待排序的文件進(jìn)行n-1趟掃描,第i趟掃描選出剩下的n-i+1個(gè)記錄,并與第i個(gè)記錄交換。 </p><p><b> Heap();</b></p><p> 初始條件:數(shù)組已經(jīng)存在。</p
16、><p> 基本思想:對(duì)一組待排序的的鍵值,首先是把它們按堆的定義排列成一個(gè)序列(稱為初建堆),這就找到了最小鍵值,然后把最小的鍵值取出,用剩下的鍵值再重建堆,便得到次小鍵值,如此反復(fù)進(jìn)行,知道把全部鍵值排好序?yàn)橹埂?lt;/p><p><b> }ADT 排序</b></p><p><b> 3.2模塊劃分</b><
17、;/p><p> 本程序包括兩個(gè)模塊:</p><p><b> (1)主程序模塊</b></p><p> void main()</p><p><b> {</b></p><p><b> 初始化;</b></p><p
18、><b> 隨機(jī)數(shù)的產(chǎn)生;</b></p><p><b> 調(diào)用子函數(shù)</b></p><p><b> };</b></p><p> (2)子函數(shù)模塊:實(shí)現(xiàn)直接插入排序的抽象數(shù)據(jù)類型。</p><p> 實(shí)現(xiàn)希爾排序的抽象數(shù)據(jù)類型。</p>
19、<p> 實(shí)現(xiàn)冒泡排序的抽象數(shù)據(jù)類型。</p><p> 實(shí)現(xiàn)快速排序的抽象數(shù)據(jù)類型。</p><p> 實(shí)現(xiàn)選擇排序的抽象數(shù)據(jù)類型。</p><p> 實(shí)現(xiàn)堆排序的抽象數(shù)據(jù)類型。</p><p> 最后輸出相應(yīng)算法的比較次數(shù)(至少有五種不同的數(shù)據(jù))和移動(dòng)次數(shù)(關(guān)鍵字的交換記為三次移動(dòng))。從而直觀的判斷各內(nèi)部排序算法性能的
20、優(yōu)劣性。</p><p><b> 4 詳細(xì)設(shè)計(jì)</b></p><p> 4.1數(shù)據(jù)類型的定義</p><p> (1)直接插入排序類型:</p><p> void Insertsort();</p><p> (2)希爾排序類型:</p><p> voi
21、d Shellsort();</p><p> (3)冒泡排序類型:</p><p> void Bubblesort();</p><p> (4)快速排序類型:</p><p> void QuickSort(int low,int high);</p><p> (5)選擇排序類型:</p>
22、<p> void Selectsort();</p><p><b> (6)堆排序類型:</b></p><p> void Heap();</p><p> 4.2主要模塊的算法描述</p><p> 下面是主程序的結(jié)構(gòu)圖和幾個(gè)主要模塊的流程圖:</p><p>&l
23、t;b> 循環(huán)</b></p><p> 4.21主程序結(jié)構(gòu)圖 </p><p><b> N</b></p><p> N Y </p><p><b> Y </b></p><
24、;p><b> N</b></p><p><b> Y</b></p><p> 4.22冒泡排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖</p><p><b> N</b></p><p><b> Y</b></p><
25、p> 4.23選擇排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖</p><p><b> N</b></p><p><b> Y</b></p><p> 4.24堆排序關(guān)鍵字比較次數(shù)和移動(dòng)次數(shù)的流程圖</p><p><b> 5 測(cè)試分析</b></p>
26、;<p> 進(jìn)行了99趟排序后,得到了最終的排序結(jié)果,并且也知道了直接插入排序的比較次數(shù)和移動(dòng)次數(shù)</p><p> 了解了直接插入排序的性能后,下面是希爾排序的性能比較:</p><p> 了解了希爾排序的性能后,下面是冒泡排序的性能比較:</p><p> 了解了冒泡排序的性能后,下面是快速排序的性能比較:</p><p
27、> 了解了快速排序的性能后,下面是選擇排序的性能比較:</p><p> 了解了選擇排序的性能后,下面是堆排序的性能比較:</p><p> 以上就是對(duì)六種排序算法的一種演示,經(jīng)過(guò)觀察和分析我們可以比較六種排序的性能。</p><p><b> 6 課程設(shè)計(jì)總結(jié)</b></p><p> 通過(guò)本次課程設(shè)計(jì)
28、,我對(duì)直接插入排序,希爾排序,選擇排序等六種排序的概念有了一個(gè)新的認(rèn)識(shí),也慢慢地體會(huì)到了它們之間的奧妙。這次的課程設(shè)計(jì),加強(qiáng)了我的動(dòng)手,思考和解決問(wèn)題的能力。鞏固和加深了我對(duì)數(shù)據(jù)結(jié)構(gòu)的理解,也讓我懂得了理論與實(shí)際相結(jié)合是非常重要的,更讓我進(jìn)一步明白了“團(tuán)結(jié)就是力量”這句話的含義。</p><p> 在整個(gè)設(shè)計(jì)過(guò)程中,構(gòu)思是很花時(shí)間的。調(diào)試時(shí)經(jīng)常會(huì)遇到這樣那樣的錯(cuò)誤,有的是因?yàn)榇中脑斐傻恼Z(yǔ)法錯(cuò)誤。當(dāng)然,很多是因?yàn)?/p>
29、用錯(cuò)了方法,總是實(shí)現(xiàn)不了。同時(shí)在設(shè)計(jì)過(guò)程中發(fā)現(xiàn)了自己的不足之處,對(duì)以前所學(xué)過(guò)的知識(shí)理解的不夠深刻,掌握的不夠透徹。</p><p> 根據(jù)我在課程設(shè)計(jì)中遇到的問(wèn)題,我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn):</p><p> 1、多在實(shí)踐中鍛煉自己;</p><p> 2、寫(xiě)程序的過(guò)程中要考慮周到;</p><p> 3、在做設(shè)計(jì)的時(shí)候要有
30、信心,有耐心,切勿浮躁。</p><p> 此次的課程設(shè)計(jì)得以順利完成,與黃同成老師的耐心指導(dǎo)和同學(xué)們的及時(shí)幫助是分不開(kāi)的。當(dāng)我在編寫(xiě)程序遇到難題時(shí),是黃老師的耐心指導(dǎo),我才可以突破一個(gè)個(gè)難關(guān)。在程序設(shè)計(jì)過(guò)程中,同學(xué)們給我的鼓勵(lì)和幫助使我信心倍增。在此我再次向黃同成老師和熱心幫助我的同學(xué)表示深深的謝意。</p><p><b> 參考文獻(xiàn)</b></p>
31、;<p> [1] 黃同成,黃俊民,董建寅.?dāng)?shù)據(jù)結(jié)構(gòu)[M].北京:中國(guó)電力出版社,2008</p><p> [2] 董建寅,黃俊民,黃同成.?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)與題解[M].北京:中國(guó)電力出版社,2008</p><p> [3] 嚴(yán)蔚敏,吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M]. 北京:清華大學(xué)出版社,2002</p><p> [4] 劉振鵬,張
32、曉莉,郝杰.?dāng)?shù)據(jù)結(jié)構(gòu)[M].北京:中國(guó)鐵道出版社,2003</p><p><b> 附錄(源程序清單)</b></p><p> #include <stdio.h></p><p> #include <stdlib.h></p><p> #include <math.h>
33、;</p><p> #include <time.h></p><p> #define L 100</p><p> #define FALSE 0</p><p> #define TRUE 1</p><p> /*typedef struct</p><p>&
34、lt;b> {</b></p><p><b> int key;</b></p><p> char otherinfo;</p><p> }RecType;*/</p><p> //typedef RecType Seqlist[L+1];</p><p>
35、int s[100],R[100];</p><p><b> int num;</b></p><p> int times=0,changes=0;</p><p> //Seqlist R;</p><p> void Insertsort();</p><p> void Bub
36、blesort();</p><p> void QuickSort(int low,int high);</p><p> void Shellsort();</p><p> void Selectsort();</p><p> void Heap();</p><p> int Partition()
37、;</p><p> void main()</p><p><b> {</b></p><p> //Seqlist S;</p><p><b> int i,k;</b></p><p> char ch1,ch2,q;</p><p&g
38、t; printf("產(chǎn)生100個(gè)隨機(jī)數(shù):\n");</p><p> srand((unsigned)time(NULL));</p><p> for(i=1;i<=L;i++)</p><p><b> {</b></p><p> s[i]=rand()%100;</p&
39、gt;<p><b> }</b></p><p> for(i=1;i<=L;i++)</p><p><b> {</b></p><p> printf("%4d",s[i]);</p><p><b> }</b><
40、;/p><p> printf("\n\t排序數(shù)據(jù)已經(jīng)輸入完畢!");</p><p> for(i=1;i<=L;i++)</p><p> R[i]=s[i];</p><p><b> ch1='y';</b></p><p> while (
41、ch1=='y'||ch1=='Y')</p><p><b> {</b></p><p> printf("\n\n\n\n\n\t\t\t排 序 性 能 分 析\n");</p><p> printf("\t\t*****************************
42、**********\n");</p><p> printf("\t\t* 1--------直接插入排序 ---------*\n");</p><p> printf("\t\t* 2--------希 爾 排 序 ---------*\n");</p><p> printf(&q
43、uot;\t\t* 3--------冒 泡 排 序 ---------*\n");</p><p> printf("\t\t* 4--------快 速 排 序----------*\n");</p><p> printf("\t\t* 5--------選 擇 排 序 ---------*\n"
44、;);</p><p> printf("\t\t* 6--------堆 排 序----------*\n");</p><p> printf("\t\t* 0--------返 回----------*\n");</p><p> printf("\t\t****
45、***********************************\n");</p><p> printf("\t\t請(qǐng)選擇菜單號(hào)(0---6):");</p><p> scanf("%c",&ch2);getchar();</p><p> for(i=1;i<=L;i++)</p
46、><p> R[i]=s[i];</p><p> switch(ch2)</p><p><b> {</b></p><p> case '1':Insertsort();break;</p><p> case '2':Shellsort();break
47、;</p><p> case '3':Bubblesort();break;</p><p><b> case '4':</b></p><p> printf("\n\t\t尚未排序的數(shù)據(jù)為(回車(chē)?yán)^續(xù)):");</p><p> for(k=1;k<
48、=L;k++)</p><p> printf("%5d",R[k]);</p><p> getchar();printf("\n");</p><p> num=0;QuickSort(1,L);</p><p><b> break;</b></p>&
49、lt;p> case '5':Selectsort();break;</p><p> case '6':Heap();break;</p><p> case '0':ch1='n';break;</p><p> default:printf("\t\t輸入錯(cuò)誤!請(qǐng)重新輸入!
50、\n\t\t");</p><p><b> }</b></p><p> if(ch2!='0')</p><p><b> {</b></p><p> if(ch2=='2'||ch2=='3'||ch2=='4'
51、;||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')</p><p> printf("\n\t排序演示輸出完畢!\n");</p><p> printf("\n\t請(qǐng)按回車(chē)鍵返回主菜單...");</p><p> q=g
52、etchar();</p><p> if (q!='\xA')</p><p><b> {</b></p><p> getchar();ch1='n';</p><p><b> }</b></p><p><b>
53、}</b></p><p><b> }</b></p><p><b> }</b></p><p> void Insertsort()//直接插入排序</p><p><b> {</b></p><p> int i,j,k
54、,m=0;</p><p> printf("\n\t\t尚未排序的數(shù)據(jù)為(回車(chē)?yán)^續(xù)):");</p><p> for(k=1;k<=L;k++)</p><p> printf("%5d",R[k]);</p><p> getchar();</p><p>
55、 printf("\n");</p><p> for(i=2;i<=L;i++)</p><p><b> {</b></p><p> if(R[i]<R[i-1])</p><p><b> { </b></p><p&g
56、t; R[0]=R[i];j=i-1;</p><p> while(R[0]<R[j])</p><p><b> {</b></p><p><b> times++; </b></p><p> changes++;</p><p> R[j+1]=R
57、[j];j--;</p><p><b> }</b></p><p> R[j+1]=R[0];</p><p> changes++;</p><p><b> }</b></p><p> m++; times++;</p><p>
58、;<b> }</b></p><p> printf("\n\n");</p><p> printf("\t最終排序結(jié)果為:");</p><p> for(i=1;i<=L;i++)</p><p> printf("%5d",R[i]);
59、</p><p> printf("\n");</p><p> printf("\n\t直接插入排序的比較次數(shù)為%d",times);</p><p> printf("\n\t直接插入排序的移動(dòng)次數(shù)為%d",changes);</p><p><b> time
60、s=0;</b></p><p> changes=0;</p><p><b> }</b></p><p> void Shellsort() //希爾排序</p><p><b> {</b></p><p> int i,j,gap,x,m=0
61、,k;</p><p> printf("\n\t尚未排序的數(shù)據(jù)為(回車(chē)?yán)^續(xù)):");</p><p> for(k=1;k<=L;k++)</p><p> printf("%5d",R[k]);</p><p> getchar();</p><p> pri
62、ntf("\n");</p><p><b> gap=L/2;</b></p><p> while (gap>0)</p><p><b> {</b></p><p> for(i=gap+1;i<=L;i++)</p><p>
63、<b> {</b></p><p><b> j=i-gap;</b></p><p> while(j>0)</p><p><b> {</b></p><p><b> times++;</b></p><p&g
64、t; if (R[j]>R[j+gap])</p><p><b> {</b></p><p> x=R[j];R[j]=R[j+gap];</p><p> R[j+gap]=x;</p><p><b> j=j-gap;</b></p><p> c
65、hanges++;</p><p><b> }</b></p><p><b> else</b></p><p><b> j=0;</b></p><p><b> }</b></p><p><b> }
66、</b></p><p> gap=gap/2;</p><p><b> m++;</b></p><p><b> }</b></p><p> printf("\n\n");</p><p> printf("\t最終
67、排序結(jié)果為:");</p><p> for(i=1;i<=L;i++)</p><p> printf("%5d",R[i]);</p><p> printf("\n");</p><p> printf("\n\t希爾排序的比較次數(shù)為%d",times)
68、;</p><p> printf("\n\t希爾排序的移動(dòng)次數(shù)為%d",changes);</p><p><b> times=0; </b></p><p> changes=0;</p><p><b> }</b></p><p> v
69、oid Bubblesort()//冒泡排序</p><p><b> {</b></p><p> int i,j,k;</p><p> int exchange;</p><p> printf("\n\t\t尚未排序的數(shù)據(jù)為(回車(chē)?yán)^續(xù)):");</p><p>
70、 for(k=1;k<=L;k++)</p><p> printf("%5d",R[k]);</p><p> getchar();</p><p> printf("\n");</p><p> for(i=1;i<=L;i++)</p><p><
71、;b> {</b></p><p> exchange=FALSE;</p><p> for(j=L;j>=i+1;j--)</p><p><b> {</b></p><p><b> times++;</b></p><p> if
72、(R[j]<R[j-1])</p><p><b> { </b></p><p> R[0]=R[j];</p><p> R[j]=R[j-1];</p><p> R[j-1]=R[0];</p><p> exchange=TRUE;</p><p>
73、; changes+=3;</p><p><b> }}</b></p><p> if(exchange);</p><p><b> } </b></p><p> printf("\n\n");</p><p> printf(&quo
74、t;\t最終排序結(jié)果為:");</p><p> for(i=1;i<=L;i++)</p><p> printf("%5d",R[i]);</p><p> printf("\n");</p><p> printf("\n\t冒泡排序的比較次數(shù)為%d",
75、times);</p><p> printf("\n\t冒泡排序的移動(dòng)次數(shù)為%d",changes);</p><p><b> times=0;</b></p><p> changes=0;</p><p><b> }</b></p><p&g
76、t; int Partition(int i,int j) //快速排序</p><p><b> {</b></p><p> int pirot=R[i];</p><p> while(i<j)</p><p><b> {</b></p><p>
77、 while(i<j&&R[j]>=pirot)</p><p><b> {j--;</b></p><p><b> times++;</b></p><p><b> }</b></p><p><b> if(i<
78、j)</b></p><p> {R[i++]=R[j];</p><p> changes++;</p><p><b> }</b></p><p> while(i<j&&R[i]<=pirot)</p><p><b> {i
79、++;</b></p><p><b> times++;</b></p><p><b> }</b></p><p><b> if(i<j)</b></p><p> {R[j--]=R[i];</p><p> ch
80、anges++;</p><p><b> }</b></p><p><b> }</b></p><p> R[i]=pirot;</p><p><b> return i;</b></p><p><b> }</b&g
81、t;</p><p> void QuickSort(int low,int high)</p><p><b> {</b></p><p> int pirotpos,k,i;</p><p> if (low<high)</p><p><b> {</b&g
82、t;</p><p> pirotpos=Partition(low,high);</p><p><b> num++;</b></p><p> QuickSort(low,pirotpos-1);</p><p> QuickSort(pirotpos+1,high);</p><p&g
83、t;<b> }</b></p><p> printf("\n\n");</p><p> printf("\t最終排序結(jié)果為:\n");</p><p> for(i=1;i<=L;i++)</p><p> printf("%5d",R[i
84、]);</p><p> printf("\n");</p><p> printf("\n\t快速排序的比較次數(shù)為%d",times);</p><p> printf("\n\t快速排序的移動(dòng)次數(shù)為%d",changes);</p><p><b> times
85、=0;</b></p><p> changes=0;</p><p><b> }</b></p><p> void Selectsort() //選擇排序</p><p><b> {</b></p><p> int i,j,k,h;</
86、p><p> printf("\n\t\t尚未排序的數(shù)據(jù)為(回車(chē)?yán)^續(xù)):");</p><p> for(k=1;k<=L;k++)</p><p> printf("%5d",R[k]);</p><p> getchar();</p><p> printf(&q
87、uot;\n");</p><p> for(i=1;i<=L;i++)</p><p><b> {</b></p><p><b> h=i;</b></p><p> for(j=i+1;j<=L;j++)</p><p> {times
88、++;</p><p> if (R[j]<R[h])</p><p><b> h=j;</b></p><p><b> if(h!=j)</b></p><p><b> {</b></p><p> R[0]=R[h];R[h]
89、=R[i];R[i]=R[0];</p><p> changes+=3;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> printf("\n\n&
90、quot;);</p><p> printf("\t最終排序結(jié)果為:");</p><p> for(i=1;i<=L;i++)</p><p> printf("%5d",R[i]);</p><p> printf("\n");</p><p&
91、gt; printf("\n\t選擇排序的比較次數(shù)為%d",times);</p><p> printf("\n\t選擇排序的比較次數(shù)為%d",changes);</p><p><b> times=0;</b></p><p> changes=0;</p><p>
92、<b> }</b></p><p> void CreateHeap(int root,int index)//建堆</p><p><b> {</b></p><p> int j,temp,finish;</p><p><b> j=2*root;</b>&
93、lt;/p><p> temp=R[root];</p><p><b> finish=0;</b></p><p> while (j<=index&&finish==0)</p><p><b> {</b></p><p> if (j&l
94、t;index)</p><p> if (R[j]<R[j+1])</p><p><b> {</b></p><p><b> j++;</b></p><p><b> times++;</b></p><p><b>
95、 }</b></p><p> if(temp>=R[j])</p><p><b> {</b></p><p> finish=1; //堆建立完成</p><p><b> times++;</b></p><p><b> }
96、</b></p><p><b> else</b></p><p><b> {</b></p><p> R[j/2]=R[j];//父結(jié)點(diǎn)=當(dāng)前結(jié)點(diǎn)</p><p><b> j=j*2;</b></p><p> chang
97、es++;</p><p><b> }</b></p><p><b> }</b></p><p> R[j/2]=temp; //父結(jié)點(diǎn)=root值</p><p><b> }</b></p><p> void HeapSort
98、()</p><p><b> {</b></p><p> int i,j,temp,k;</p><p> for(i=(L/2);i>=1;i--)//將二叉樹(shù)轉(zhuǎn)換成堆</p><p> CreateHeap(i,L);//建堆</p><p> for(i=L-1,k=1;
99、i>=1;i--,k++)</p><p><b> {</b></p><p> temp=R[i+1];//堆(heap)的root值和最后一個(gè)值交換</p><p> R[i+1]=R[1];</p><p> R[1]=temp;</p><p> changes+=3;&
100、lt;/p><p> CreateHeap(1,i);</p><p><b> }</b></p><p><b> }</b></p><p> void Heap()</p><p><b> { int k;</b></p>
101、<p> printf("\n\t尚未排序的數(shù)據(jù)為(回車(chē)?yán)^續(xù)):");</p><p> for(k=1;k<=L;k++)</p><p> printf("%5d",R[k]);</p><p> printf("\n\t");</p><p> get
102、char();</p><p> HeapSort();</p><p> printf("\n\n");</p><p> printf("\t最終排序結(jié)果為:");</p><p> for(k=1;k<=L;k++)</p><p> printf(&quo
103、t;%5d",R[k]);</p><p> printf("\n");</p><p> printf("\n\t堆排序的比較次數(shù)為%d",times);</p><p> printf("\n\t堆排序的移動(dòng)次數(shù)為%d",changes);</p><p><
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---幾種排序算法的演示
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--內(nèi)部排序算法的性能分析
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--幾種排序算法的演示
- 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告---排序算法的實(shí)現(xiàn)與比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序算法的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----內(nèi)部排序算法性能分析
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告內(nèi)部排序的算法設(shè)計(jì)與分析
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告--排序
- 拓?fù)渑判?算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì))
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法比較
- 數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告---圖的算法實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)排序綜合課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--內(nèi)部排序算法的比較
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--排序算法演示系統(tǒng)
- 數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)報(bào)告
評(píng)論
0/150
提交評(píng)論