2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩25頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論