數(shù)據(jù)結(jié)構(gòu)課程設計排序算法演示系統(tǒng)方案

1、學習參考計算機學院數(shù)據(jù)結(jié)構(gòu)課程設計題目：數(shù)據(jù)結(jié)構(gòu)排序算法演示系統(tǒng)班級：姓名：學號：同組人女起迄日期：課程設計地點：指導教師：評閱意見：成績評定：評閱人：日期：完成日期：2014年12月目錄TOC o 1-5 h z一、課程設計的目的1 HYPERLINK l bookmark4 二、設計內(nèi)容和要求1三、數(shù)據(jù)采取的結(jié)構(gòu)1 HYPERLINK l bookmark8 四、功能模塊詳細設計1詳細設計思想2冒泡排序5快速排序7直接插入排序9希爾排序10直接選擇排序12堆排序144.1.7歸并排序17 HYPERLINK l bookmark10 五、總結(jié)或心得體會19 HYPERLINK l book

2、mark12 六、參考文獻20七、附錄20word格式整理版設計目的隨著計算機技術(shù)的發(fā)展，各種排序算法不斷的被提出。排序算法在計算機科學中有非常重要的意義，且應用很廣泛。在以后的發(fā)展中排序?qū)ξ覀兊膶W習和生活的影響會逐漸增大，很有必要學習排序知識。此次課程設計一方面使自己掌握排序的知識，另一方面鍛煉一下團隊合作開發(fā)系統(tǒng)的能力。設計內(nèi)容和要求功能要求：界面友好，易與操作?？刹捎貌藛位蚱渌藱C對話方式進行選擇。實現(xiàn)各種內(nèi)部排序。包括直接插入排序，冒泡排序，直接選擇排序，希爾排序，快速排序，堆排序，歸并排序。待排序的元素的關(guān)鍵字為整數(shù)或(字符)?？捎秒S機數(shù)據(jù)和用戶輸入數(shù)據(jù)作測試比較。比較的指標為有關(guān)鍵

3、字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)(關(guān)鍵字交換以3次計)。(1)演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標值的列表，以便比較各種排序的優(yōu)劣。本設計所采用的數(shù)據(jù)結(jié)構(gòu)typedefstructintkey;RecType;功能模塊詳細設計排序算法演示系統(tǒng)學習參考-T-word格式整理版學習參考4.1詳細設計思想主函數(shù)：#include#include#include#defineL8/排序元素個數(shù)#defineFALSE0#defineTRUE1typedefstructintkey;RecType;RecTypeRL;intnum;intsum;intsun;/定義排序趟數(shù)的全局

4、變量/系統(tǒng)主界面/主函數(shù)intmain()RecTypeS100;inti,k;charch1,ch2,q;printf(ntt*排序算法演示系統(tǒng)*nntt請輸入%d個待排序的數(shù)據(jù)：n,L);for(i=1;i=L;i+)printf(tt請輸入第小七人數(shù)據(jù)：，i);scanf(%d,&Si.key);getchar();ch1=y;while(ch1=y)printf(ntt菜單n);printf(ntt*n)printf(ntt*1更新排序數(shù)據(jù)*2直接插入排序n);printf(ntt*3希爾排序*4冒泡排序n);printf(ntt*5快速排序*6直接選擇排序n);printf(ntt*

5、7堆排序*8歸并排序n);printf(ntt*0退出*n);printf(ntt*n);printf(ntt請選擇：)；scanf(%c,&ch2);getchar()；for(i=1；i=L；i+)Ri.key=Si.key；switch(ch2)case1:printf(ntt請輸入%d個待排序數(shù)據(jù)ntt,L);for(i=1;i=L;i+)scanf(%d,&Si.key);getchar();printf(tt);printf(ntt數(shù)據(jù)輸入完畢！)；break;case2:Insertsort();break;case3:Shellsort();break;case4:Bubble

6、sort();break;case5:printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);num=0;sun=0;sum=0;Quicksort(1,L);printf(ntt排序最終結(jié)果是：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);printf(ntt比較次數(shù)是：%dntt,sum);printf(ntt交換次數(shù)是：%dntt,sun);break;case6:Selectsort();break;91-79case7:Heap();bre

7、ak;case8:Mergesort();break;case0:ch1=n;break;default:system(cls);/清屏printf(ntt對不起，您輸入有誤，請重新輸入！n);break;if(ch2!=0)if(ch2=2|ch2=3|ch2=4|ch2=5|ch2=6|ch2=7|ch2=8)printf(nntt排序完畢！)；printf(ntt按回車鍵繼續(xù)！)；q=getchar();if(q!=n)getchar();ch1=n;return1;費入第1th數(shù);居|入第眥h數(shù)據(jù)汶|入第眥h數(shù)嶠汁看入罷4th數(shù)嶠：4卷入義訕數(shù)湄汚卷入第&訕數(shù)湄汴卷入第?訕數(shù)湄汐裔入第

8、眥h數(shù)馮汁菜單1更新排序數(shù)據(jù)3希爾排序5快速排序?堆排序2直接插入排序4冒泡排序6直接選擇排序8歸并排序退nhw0I屮IkkkkkkkkkkkkRD:Debugyan.exer,圖一主界面請請請請請請請請4.1.1冒泡排序核心思想依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面，第一輪比較后，最大的數(shù)便被放到了最后；第二輪操作前n-1個數(shù)據(jù)(假設有n個數(shù)據(jù))，依然是依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面，倒數(shù)第二個數(shù)便是第二大的數(shù)；同理第i輪操作前n-i+1的數(shù)據(jù)(假設i取值是從1開始的)，則n-i+i位置上的數(shù)據(jù)為第i大的數(shù)據(jù)。一共有n-1輪，第i輪比較中共比較n-i次比較。核

9、心代碼voidBubblesort()inti,j,k,x=0,y=0,m=0;intexchange=TRUE;/標志位exchange初始化為TRUE1printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;iL&exchange=TRUE;i+)/外層對總的循環(huán)次數(shù)執(zhí)行次數(shù)exchange=FALSE;for(j=1;j=L+1-i;j+)/內(nèi)層相鄰記錄的交換與比較m+;/比較次數(shù)+if(Rj.keyRj-1.key)R0.key=Rj.key;Rj.key=

10、Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移動次數(shù)+m-;/比較次數(shù)if(exchange)/輸出語句printf(tt第d趟冒泡排序的結(jié)果為：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(ntt比較次數(shù)是：tt);printf(%d,m);printf(ntt移動次數(shù)是：tt);printf(%d,y);printf(ntt排序最終結(jié)果是：ntt);for(i=l;i=L;i+)printf(%5d,Ri.key);D:Debugyan.exenTOC o 1

11、-5 h z1234第鍛直接描入排底的結(jié)杲為=12345較前肓捋插代排產(chǎn)F勺結(jié)卑九12345第謹直接恬入排序的結(jié)果九12345第璀直按插入排圧F勺結(jié)黑為:12345m是ffi.K孝壽1圖二直接插入排序4.1.2快速排序核心思想首先檢查數(shù)據(jù)列表中的數(shù)據(jù)數(shù)，如果小于兩個，則直接退出程序。如果有超過兩個以上的數(shù)據(jù)，就選擇一個分割點將數(shù)據(jù)分成兩個部分，小于分割點的數(shù)據(jù)word格式整理版word格式整理版學習參考i+;學習參考放在一組，其余的放在另一組，然后分別對兩組數(shù)據(jù)排序。通常分割點的數(shù)據(jù)是隨機選取的。這樣無論你的數(shù)據(jù)是否已被排列過，你所分割成的兩個字列表的大小是差不多的。而只要兩個子列表的大小差不

12、多核心代碼/遞歸算法實現(xiàn)voidQuicksort(intlow,inthigh)inti=low,j=high,k;R0.key=Rlow.key;while(ij)while(ij&R0.key=Rj.key)/右側(cè)掃描j-;sum+;if(ij)Ri.key=Rj.key;/交換i+;sun+;while(ij&Ri.keyR0.key)/左側(cè)掃描sum+;if(ij)Rj.key=Ri.key;/交換j-;sun+;Ri.key=R0.key;num+;/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第%d趟快速排序的結(jié)果為：ntt,num);for(k=1;k=L;k+)printf

13、(%5d,Rk.key);getchar();printf(n);if(lowi-1)Quicksort(low,i-l);/遞歸部分(左側(cè))if(j+lhigh)Quicksort(j+l,high);/遞歸部分(右側(cè))圖三快速排序4.1.3直接插入排序核心思想經(jīng)過i-1遍處理后，Ll.i-l己排好序。第i遍處理僅將Li插入Ll.i-1的適當位置，使得Ll.i又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較Li和Li-1，如果Li-lWLi，則Ll.i已排好序，第i遍處理就結(jié)束了；否則交換Li與LiT的位置，繼續(xù)比較LiT和Li-2，直到找到某一個位置j(lWjWi-l)

14、，使得LjWLj+1時為止核心代碼voidInsertsort()inti,j,k,m=0,x=0;/初始化比較次數(shù)變量m，移動次數(shù)變量xprintf(ntt原始數(shù)據(jù)為：(按回車鍵開始排序)ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/主要運行部分for(i=2;i=L;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1=Rj;j-;Rj+1=R0;x+;m+;/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第小趟直接插入排序的結(jié)果為：ntt,m);for(k

15、=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(n);printf(ntt比較次數(shù)是：tt);printf(%d,m);printf(ntt移動次數(shù)是：tt);printf(%d,x);printf(ntt排序最終結(jié)果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);D:Debugyan.exe第3趟直接耘衣排序的結(jié)果為：2345第鍛直接描典排序的結(jié)果対:12345兼趟直接插人排序的結(jié)果為：2345第&迪宣接插人排序的結(jié)果為:12345第趟直接插入排序的結(jié)果為:12345b:廉H2詵驚取117777

16、7e888N圖四直接插入排序4.1.4希爾排序核心思想先取一個小于n的整數(shù)dl作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取第二個增量d2d1重復上述的分組和排序，直至所取的增量dt=1(dtdt-lYd2d1)，即所有記錄放在同一組中進行直接插入排序為止。核心代碼voidShellsort()inti,j,gap,x,k,y=0,m=0;/初始化比較次數(shù)變量m，移動次數(shù)變量yntt);printf(ntt原始數(shù)據(jù)為：(按回車鍵開始排序)for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+ga

17、p.key)x=Rj.key;/交換語句Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;y+;/移動次數(shù)+elsej=0;gap=gap/2;m+;/比較次數(shù)+ntt,m);/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第%d趟希爾排序的結(jié)果為：for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(ntt比較次數(shù)是：tt);printf(%d,m);printf(ntt移動次數(shù)是：tt);printf(%d,y);printf(ntt排序最終結(jié)果是：ntt);for(i=l;i=L;i+)pri

18、ntf(%5d,Ri.key);printf(n);圖五希爾排序4.1.5直接選擇排序核心思想第一次從R0Rn-1中選取最小值，與R0交換，第二次從R1Rn-1中選取最小值，與R2交換，.，第i次從Ri-1Rn-1中選取最小值，與Ri-1交換，第n-1次從Rn-2Rn-1中選取最小值，與Rn-2交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列.核心代碼voidSelectsort()inti，j，k，h，x=0，y=0;printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d，Rk.key);getchar();printf

19、(n);for(i=1;iL;i+)h=i;for(j=i+1;j=L;j+)x+;/比較次數(shù)if(Rj.keyRh.key)h=j;/確定最小值if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=R0.key;y+;/移動次數(shù)printf(tt第d趟選擇排序的結(jié)果為：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/輸出語句包括排序的結(jié)果及次數(shù)printf(ntt比較次數(shù)：d,x);printf(ntt移動次數(shù)：d,y);printf(ntt排序最終結(jié)果是：ntt);for(i=1;i

20、=L;i+)printf(%5d,Ri.key);printf(n);圖選擇排序4.1.6堆排序核心思想堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。將原始記錄序列建成一個堆，成為初始堆，并輸出堆頂元素；調(diào)整剩余的記錄序列，使之成為一個新堆，再輸出堆頂元素；如此反復進行，當堆中只有一個元素時，整個序列的排序結(jié)束，輸出的序列便是原始序列的非遞減有序序列。在堆排序的過程中，主要負責兩方面的工作：一是如何將原始記錄序列構(gòu)造成一個堆，即建立初始堆；二是輸出堆頂元素后，如何將剩余記錄整理成一個新堆。核

21、心代碼voidCreateHeap(introot,intindex,int*x,int*y)intj,temp,finish;j=2*root;/jtemp=Rroot.key;finish=0;while(j=index&finish=0)if(jindex)if(Rj.key=Rj.key)finish=1;elseRj/2.key=Rj.key;(*y)+;指向左孩子指向較大的孩子j=j*2;*x=*x+2;Rj/2.key=temp;(*y)+;/堆排序voidHeapsort()inti,j,temp,k,x=0,y=0;for(i=(L/2);i=1;i-)/建立初始堆Creat

22、eHeap(i,L,&x,&y);x=0;y=0;for(i=L-1,k=1;i=1;i-,k+)/將堆中根節(jié)點和最后一個節(jié)點交換temp=Ri+1.key;Ri+1.key=R1.key;R1.key=temp;CreateHeap(1,i,&x,&y);printf(tt第小趟堆排序的結(jié)果為：ntt,k);for(j=1;j=L;j+)printf(%5d,Rj.key);getchar();printf(n);printf(ntt比較次數(shù)是：%dtt,x);printf(ntt移動次數(shù)是：%dtt,y);voidHeap()inti;printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：n

23、tt);for(i=1;i=L;i+)printf(%5d,Ri.key);getchar();printf(n);Heapsort();word格式整理版word格式整理版學習參考(*x)+;學習參考printf(ntt排序最終結(jié)果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);voidMerge(intlow,intmm,inthigh,int*x,int*y)/兩個有序序列的合并inti=low,j=mm+1,p=0;RecType*Rl;/i對第一個開始到結(jié)尾，j從第二個開始到結(jié)尾R1=newRecTypehigh-low+1;if

24、(!Rl)printf(內(nèi)存不足！)；while(i=mm&j=high)/兩序列從起始位置開始將小的元素放入到Rl中Rlp+=(Ri.key=Rj.key)?Ri+:Rj+;(*y)+;while(i=mm)/第二段結(jié)束，剩余放入R1中R1p+=Ri+;(*y)+;while(j=high)/第二段剩余，剩余放入R1中R1p+=Rj+;(*y)+;for(p=0,i=low;i=high;p+,i+)/剩余元素放入R1中,賦予RRi=R1p;(*y)+;圖七堆排序4.1.7歸并排序核心思想將有n個記錄的原始序列看作n個有序子序列，每個子序列的長度為1，然后從第一個子序列開始，把相鄰的子序列兩

25、兩合并，得到n/2個長度為2或1的子序列(當子序列個數(shù)為奇數(shù)時，最后一組合并得到的序列長度為1)，把這一過程稱為一次歸并排序，對第一次歸并排序后的n/2個子序列采用上述方法繼續(xù)順序成對歸并，如此重復，當最后得到的長度為n的一個子序列時，該子序列便是原始序列歸并排序后的有序序列。核心代碼voidMergePass(intlength,int*x,int*y)/次二路歸并排序inti;for(i=1;i+2*length-1=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1,x,y);/函數(shù)調(diào)用if(i+length-1L)Merge(i,i+lengt

26、h-1,L,x,y);/函數(shù)調(diào)用/歸并排序voidMergesort()/二路歸并排序intlength,k,m=0,i,x=0,y=0;printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(length=1;lengthL;length*=2)MergePass(length,&x,&y);m+;/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第%d趟歸并排序的結(jié)果為：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();

27、printf(n);printf(ntt排序最終結(jié)果是：ntt);for(i=l;i=L;i+)printf(%5d,Ri.key);printf(n);printf(tt比較次數(shù)：%dn,x);printf(tt移動次數(shù)：%dn,y);圖八歸并排序總結(jié)或心得回顧這個設計過程,我學到了許多書本上沒有學到的知識。通過這次小組制作的程序,豐富了自己的實踐技能,擴展了本專業(yè)的知識面,使我受益非淺,同時也體驗到了搞軟件開發(fā)的困難度。在這次設計的同時我又從中學到了許多東西。但由于我對這樣的排序系統(tǒng)還只是一個開始，了解的不多，這其中或許還有很多的不足,在這里也懇請各位老師能夠?qū)ξ覀兊淖髌分该鞑蛔悴⒓右愿恼?/p>

28、。總之，在這一次的課程設計過程中，我們查閱了大量的資料，對數(shù)據(jù)結(jié)構(gòu)有了一點初步的認識，對于網(wǎng)絡工程這些輔助性的教材也鞏固了不少，為我們這次的課設提供了很大的幫助，鍛煉了我們的能力,讓我更加熟練了這門程序設計語言：C/C+語言，系統(tǒng)地學習了數(shù)據(jù)結(jié)構(gòu)方面的知識，并更進一步提高了我們在程序設計、調(diào)試方面的技巧。更重要的是，它還讓我們認識到了自己的不足，在編程方面，我僅僅是剛剛?cè)腴T而已，以后的道路任重道遠，需要我不斷的豐富自己、充實自己，這樣才能在程序設計方面有所收獲。在最后也感謝我們的小組成員,我在他的幫忙下順利的做好自己負責的部分.六參考文獻嚴蔚敏，吳偉明，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學出版社,2

29、007年:P263-P288。七附錄#include#include#include#defineL8/排序元素個數(shù)#defineFALSE0#defineTRUE1typedefstructintkey;RecType;RecTypeRL;intnum;intsum;intsun;/定義排序趟數(shù)的全局變量/系統(tǒng)主界面voidBubblesort()inti,j,k,x=0,y=0,m=0;intexchange=TRUE;/標志位exchange初始化為TRUE1printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);

30、getchar();printf(n);for(i=l;iL&exchange=TRUE;i+)/外層對總的循環(huán)次數(shù)執(zhí)行次數(shù)exchange=FALSE;for(j=1;j=L+1-i;j+)/內(nèi)層相鄰記錄的交換與比較m+;/比較次數(shù)+if(Rj.keyRj-1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移動次數(shù)+m-;/比較次數(shù)if(exchange)/輸出語句printf(tt第d趟冒泡排序的結(jié)果為：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar(

31、);printf(n);printf(ntt比較次數(shù)是：tt”)；printf(%d,m);printf(ntt移動次數(shù)是：tt”)；printf(%d,y)；printf(ntt排序最終結(jié)果是：ntt”)；for(i=1；i=L；i+)printf(%5d,Ri.key)；/遞歸算法實現(xiàn)voidQuicksort(intlow,inthigh)inti=low,j=high,k；R0.key=Rlow.key；while(ij)while(ij&R0.key=Rj.key)/右側(cè)掃描j-；sum+;if(ij)Ri.key=Rj.key;/交換i+;sun+;while(ij&Ri.keyR

32、0.key)/左側(cè)掃描i+;sum+;if(ij)Rj.key=Ri.key;/交換j-;sun+;Ri.key=R0.key;num+;/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第%d趟快速排序的結(jié)果為：ntt,num);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);if(lowi-l)Quicksort(low,i-l);/遞歸部分(左側(cè))if(j+lhigh)Quicksort(j+l,high);/遞歸部分(右側(cè))voidInsertsort()inti,j,k,m=0,x=0;/初始化比較次數(shù)變量m，移動次數(shù)變量xp

33、rintf(ntt原始數(shù)據(jù)為：(按回車鍵開始排序)ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/主要運行部分for(i=2;i=L;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1=Rj;j-;Rj+1=R0;x+;m+;/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第小趟直接插入排序的結(jié)果為：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(n);printf(ntt比

34、較次數(shù)是：tt);printf(%d,m);printf(ntt移動次數(shù)是：tt);printf(%d,x);printf(ntt排序最終結(jié)果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);voidShellsort()inti,j,gap,x,k,y=0,m=0;/初始化比較次數(shù)變量m，移動次數(shù)變量yprintf(ntt原始數(shù)據(jù)為：(按回車鍵開始排序)ntt);for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+gap.key)x=Rj.key;/交換語句Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;y

35、+;/移動次數(shù)+elsej=0;gap=gap/2;m+;/比較次數(shù)+/輸出語句包括排序的結(jié)果及次數(shù)printf(tt第d趟希爾排序的結(jié)果為：ntt,m);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);printf(ntt比較次數(shù)是：tt);printf(%d,m);printf(ntt移動次數(shù)是：tt);printf(%d,y);printf(ntt排序最終結(jié)果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);voidSelectsort()word格式整理版word格式整理版學

36、習參考Ri.key=Rh.key;學習參考inti,j,k,h,x=0,y=0;printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;iL;i+)h=i;for(j=i+1;j=L;j+)x+;/比較次數(shù)if(Rj.keyRh.key)h=j;/確定最小值if(h!=i)R0.key=Ri.key;Rh.key=R0.key;y+;/移動次數(shù)printf(tt第d趟選擇排序的結(jié)果為：ntt,i);for(k=1;k=L;k+)printf(%5d,Rk.key);

37、getchar();printf(n);/輸出語句包括排序的結(jié)果及次數(shù)printf(ntt比較次數(shù)：d,x);printf(ntt移動次數(shù)：d,y);printf(ntt排序最終結(jié)果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(n);voidCreateHeap(introot,intindex,int*x,int*y)word格式整理版word格式整理版R1.key=temp;學習參考Rj/2.key=Rj.key;學習參考/j指向左孩子/指向較大的孩子intj,temp,finish;j=2*root;temp=Rroot.key;fini

38、sh=0;while(j=index&finish=0)if(jindex)if(Rj.key=Rj.key)finish=1;else(*y)+;j=j*2;*x=*x+2;Rj/2.key=temp;(*y)+;/堆排序voidHeapsort()inti,j,temp,k,x=0,y=0;for(i=(L/2);i=1;i-)/建立初始堆CreateHeap(i,L,&x,&y);x=0;y=0;for(i=L-1,k=1;i=1;i-,k+)/將堆中根節(jié)點和最后一個節(jié)點交換temp=Ri+1.key;Ri+1.key=R1.key;word格式整理版學習參考CreateHeap(1,i

39、,&x,&y);printf(tt第小趟堆排序的結(jié)果為：ntt,k);for(j=1;j=L;j+)printf(%5d,Rj.key);getchar();printf(n);printf(ntt比較次數(shù)是：%dtt,x);printf(ntt移動次數(shù)是：%dtt,y);voidHeap()inti;printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(i=1;i=L;i+)printf(%5d,Ri.key);getchar();printf(n);Heapsort();printf(ntt排序最終結(jié)果是：ntt);for(i=1;i=L;i+)printf(%5d,Ri.

40、key);printf(n);voidMerge(intlow,intmm,inthigh,int*x,int*y)/兩個有序序列的合并inti=low,j=mm+1,p=0;RecType*R1;/i對第一個開始到結(jié)尾，j從第二個開始到結(jié)尾R1=newRecTypehigh-low+1;if(!R1)printf(內(nèi)存不足！)；while(i=mm&j=high)/兩序列從起始位置開始將小的元素放入到R1中R1p+=(Ri.key=Rj.key)?Ri+:Rj+;(*x)+;(*y)+;while(i=mm)/第二段結(jié)束，剩余放入R1中R1p+=Ri+;(*y)+;while(j=high)

41、/第二段剩余，剩余放入R1中R1p+=Rj+;(*y)+;for(p=0,i=low;i=high;p+,i+)/剩余元素放入R1中,賦予RRi=R1p;(*y)+;voidMergePass(intlength,int*x,int*y)/次二路歸并排序inti;for(i=1;i+2*length-1=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1,x,y);/函數(shù)調(diào)用if(i+length-1L)Merge(i,i+length-1,L,x,y);/函數(shù)調(diào)用/歸并排序voidMergesort()/二路歸并排序intlength,k,m=0,i,x=0,y=0;printf(ntt原始數(shù)據(jù)為(按回車鍵開始排序)：ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(leng