1、精選優質文檔-傾情為你奉上學 院××××學院班 級××××××××學 號××××××××姓 名×××目錄1 摘要1.1 設計題目算法型大作業題目：編寫七種排序算法的演示程序。1.2 設計內容編寫快速排序、插入排序、選擇排序、冒泡排序、堆排序、歸并排序、基數排序函數，通過主函數調用以實現七種排序算法的演示。1.3 開發工具Visual C+ 6.01.4 應用平臺Win

2、dows 2000/XP/Vista 32位2 詳細設計2.1 程序結構程序的整體結構與流程見下圖所示。程序運行時在主菜單中輸入序號選擇排序方法或選擇結束程序，當進行某種排序方法后，在主函數中輸入待排數據個數和待排數據，通過調用對應的排序函數實現排序并輸出。該排序結束后再次進入主函數，通過循環重復上述操作。其中，主函數中將數組地址和待排序數據個數傳遞給排序函數，在排序函數中實現排序功能。輸出排序結果開始快速插入選擇冒泡堆排歸并基數選擇排序方法進入主菜單退出系統2.2 主要功能函數的功能為對快速排序、插入排序、選擇排序、冒泡排序、堆排序、歸并排序、基數排序算法的演示。主函數：程序運行時，可使運行

3、者根據提醒輸入相關操作，從而進入不同的排序方法或者退出?？焖倥判蚝瘮担焊鶕焖倥判虻乃惴ǎ詈筝敵霾迦肱判蚝瘮担焊鶕迦肱判虻乃惴?，最后輸出選擇排序函數：根據選擇排序的算法，最后輸出冒泡排序函數：根據冒泡排序的算法，最后輸出堆排序函數：根據堆排序的算法，最后輸出歸并排序函數：根據歸并排序的算法，最后輸出基數排序函數：根據基數排序的算法，最后輸出2.3 函數實現主函數:在主函數中對菜單輸出，通過switch語句中的case分支選擇所需要的排序方法；通過while循環使演示程序在運行時能夠持續進行快速排序： 快速排序（kuaisu）又被稱做分區交換排序，這是一種平均性能非常好的排序方法。其算法基本

4、思想是：任取排序表中的某個數據元素(例如取第一個數據元素)作為基準，按照該數據元素的關鍵字大小，將整個排序表劃分為左右兩個子表： 左側子表中所有數據元素的關鍵字都小于基準數據元素的關鍵字。右側子表中所有數據元素的關鍵字都大于或等于基準數據元素的關鍵字，基準數據元素則排在這兩個子表中間(這也是該數據元素最終應安放的位置)，然后分別對這兩個子表重復施行上述方法的快速排序，直到所有的子表長度為1，則排序結束。插入排序：插入排序（charu）的基本思想：開始時把第一個數據元素作為初始的有序序列，然后從第二個數據元素開始依次把數據元素按關鍵字大小插入到已排序的部分排序表的適當位置。當插入第i(1<

5、i<=n)個數據元素時，前面的i-1個數據元素已經排好序，這時，用第i個數據元素的關鍵字與前面的i-1個數據元素的關鍵字順序進行比較，找到插入位置后就將第i個數據元素插入。如此進行n-1次插入，就完成了排序。以下是在順序表上實現的直接插入排序在順序表上進行直接插入排序時，當插入第i(1<i<=n)個數據元素時，前面的A0、A1、Ai-2已經排好序，這時，用Ai-1的關鍵字依次與Ai-2,Ai-3,的關鍵字順序進行比較，如果這些數據元素的關鍵字大于Ai-1的關鍵字，則將數據元素向后移一個位置，當找到插入位置后就將Ai-1插入，就完成了A0,A1,An-1的排序。選擇排序選擇排序

6、（xuanze）的算法基本思想是：a)開始時設i的初始值為0。b)如果i<n-1，在數據元素序列Ai(An-1中，選出具有最小關鍵字的數據元素Ak；否則算法結束。c)若Ak不是這組數據元素中的第一個數據元素（ik），則將Ak與Ai這兩數據元素的位置對調；d)令i=i+1轉步驟 b)。冒泡排序：冒泡排序(maopao) 的基本思想是：設排序表中有n個數據元素。首先對排序表中第一，二個數據元素的關鍵字A0和A1進行比較。如果前者大于后者，則進行交換；然后對第二，三個數據做同樣的處理；重復此過程直到處理完最后兩個相鄰的數據元素。我們稱之為一趟冒泡，它將關鍵字最大的元素移到排序表的最后一個位置，

7、其他數據元素一般也都向排序的最終位置移動。然后進行第二趟排序，對排序表中前n-1個元素進行與上述同樣的操作，其結果使整個排序表中關鍵字次大的數據元素被移到An-2的位置。如此最多做n-1趟冒泡就能把所有數據元素排好序。堆排序：堆排序(duipai)sa.對排序表中的數據元素，利用堆的調整算法形成初始堆。b.輸出堆頂元素。c.對剩余元素重新調整形成堆。d.重復執行第b、c步，直到所有數據元素被輸出。如果建立的堆滿足最大堆的條件，則堆的第一個數據元素A0具有最大的關鍵字，將A0與An-1對調，把具有最大關鍵字的數據元素交換到最后，再對前面的n-1個數據元素使用堆的調整算法，重新建立最大堆，結果把具

8、有次最大關鍵字的數據元素又上浮到堆頂，即A 0的位置，再對調A0和An-2，如此反復執行n-1次，最后得到全部排序好的數據元素序列。歸并排序：其基本思想是：設有兩個有序表A和B，其數據元素個數（表長）分別為n和m，變量i和j分別是表A和表B的當前檢測指針；設表C是歸并后的新有序表，變量k是它的當前存放指針。開始時i、j、k都分別指向A、B、C三個表的起始位置；然后根據Ai與Bj的關鍵字的大小，把關鍵字小的數據元素放到新表Ck中；且相應的檢測指針（i或j）和存放指針k增加1.如此循環，當i與j中有一個已經超出表長時，將另一個表中的剩余部分照抄到新表CkCm+n中。下面的歸并算法中，兩個待歸并的有

9、序表首尾相接存放在數組sourcetable.arr中，其中第一個表的下標范圍從left到mid，另一個表的下標范圍從mid+1到right。前一個表中有mid-left+1個數據元素，后一個表中有right mid個數據元素。歸并后得到的新有序表有right mid個數據元素。歸并后得到的新有序表存放在另一個輔助數組mergedtable.arr中，其下標范圍從left到right。一趟歸并算法：設數組sourcetable.arr0到sourcetable.arrn-1中的n個數據元素已經分為一些長度為len的歸并項，將這些歸并項兩兩歸并，歸并成一些長度為2len的歸并項，結果放到merg

10、edtable.arr中。如果n不是2len的整數倍，則一趟歸并到最后，可能遇到兩種情況：剩下一個長度為len的歸并項和一個長度不足len的歸并項，可用一次merge算法，將它們歸并成一個長度小于2len的歸并項。只剩下一個歸并項，其長度小于或等于len，可將它直接復制到數組mergedtable.arr中。在一趟歸并算法的基礎上，實現兩路歸并排序算法。在兩路歸并排序算法中，初始排序表存放在數組table.arr中,第一趟歸并將table.arr中的歸并項兩兩歸并，結果存放在輔助數組temptable.arr中。第二趟將temptable.arr中的歸并項兩兩歸并，結果放回原數組table.a

11、rr中，如此反復進行。為了將最后歸并結果仍放在數組table.arr中，歸并趟數應為偶數。如果做奇數趟就能完成時，最后還需要執行一次一趟歸并過程，由于這時的歸并項長度len>=n，因此在則趟歸并中while循環不執行，只做把temptable.arr中的數據元素復制到table.arr的工作?；鶖蹬判颍骸盎鶖蹬判蚍ā保╮adix sort）則是屬于“分配式排序”（distribution sort），基數排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其

12、時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的比較性排序法。具體可以參看后面的代碼進行理解。其它：使用了stdlib頭文件里包含的系統函數，包括清屏函數和運行時的暫停，增強了程序運行時的效果。2.4 開發日志在老師布置了大作業的題目后，我就把題目下載下來并進行分析已選擇合適的題目。經過我的慎重考慮，選擇了算法型大作業題目中的編寫七種排序算法的演示程序，覺得自己有能力把這道題目很好完成。在認真分析連題目后，基本確定了整體的思路，但是其中有堆排序，歸并排序，基數排序我沒有在教材中接觸過，于是借助了圖書館和網絡上的資源，重點對這三的函數

13、進行編寫。在編寫大作業過程中大的困難我沒有遇到，只是有些小的疏忽常常導致程序無法運行，如形參和實參的不一致等。我也在其中意識到對知識掌握的不夠熟練，在解決了這些問題后，我覺得自己對程序的編寫更加熟練了，對問題的分析也更加嚴謹了。在C程序設計的實驗和理論考試之前代碼已基本完成。在考試結束后，我又對程序稍微進行了修改，使之運行時效果更好。接著開始寫實驗報告，整理自己的大作業。我對我的作業是很滿意的。3 程序調試及運行3.1 程序運行結果1.進入程序運行后所顯示的菜單：2.快速排序：3.插入排序：4.選擇排序：5.冒泡排序：6.堆排序：7.歸并排序：8.基數排序：9.結束：3.2 程序使用說明1.打

14、開源程序，調試完畢后開始運行，開始進行七種算法的演示；2.按照說明進行輸入,選擇數字17即可進入相應的排序算法演示程序，選擇8結束程序；3.選擇排序的方法后，按要求輸入待排數據的個數，然后輸入待排序數據即可（數據排序結束后，會自動清屏，進入菜單進行接下來的選擇）；4.應當注意，本演示程序對數據進行的是升序；3.3 程序開發總結在選擇這個題目時，我覺得難度系數10對我有挑戰性，并且我對排序有相對比較熟悉，所以就選了這個題目。但是在編寫過程中卻遇到很多問題。我和我的同學進行了討論，查閱了圖書館和網絡上的資料，結合力我個人對本題目的理解對各種問題進行了處理，學到了很多教材上沒有的知識。從這次實踐中，

15、我意識到自己還有很多不足之處。能力也得到了提高。我在進行編程時還需要翻書查找，對于這一點，只能說對知識的學習還不夠扎實，所以有空時還應該繼續熟悉這門課程。另外，就是對于錯誤的處理，不能得心應手，不能正確處理一些簡單的錯誤。對于邏輯上的錯誤，不能夠立即找到出錯點，往往需要向同學請教才能找出錯誤，并且改正。我覺得這是自己獨自思考能力不高的問題，遇事需要自己仔細想想，若還不能改正，再請教別人也不遲。從總體上說，最終結果我很滿意，我覺得我所設計的程序操作方便，功能良好。我在上面花費了很多時間和精力，對作業不斷進行修改和完善，我很有成就感 。我的能力在這之中得到了提高。4 附件（源程序）# includ

16、e<stdio.h># include<stdlib.h>/*快速排序*/void kuaisu(int A,int n)int i,j,k,t,p;for(i=0;i<n-1;i+)k=i;for(j=i+1;j<n;j+)if(Aj<Ak) k=j;t=Ak;Ak=Ai;Ai=t;printf("第%d趟:",i+1);for(p=0;p<n;p+)printf("%d ",Ap);printf("n");printf("n排序結果:");for(i=0;i<

17、;n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*插入排序*/void charu(int A,int n) int i,k,t,j,h=1;for(i=1;i<n;i+)t=Ai;k=i-1;while(t<Ak)Ak+1=Ak;k-;if(k=-1)break;printf("第%d趟:",h+);for(j=0;j<n;j+)printf(&qu

18、ot;%d ",Aj);printf("n");Ak+1=t;printf("n排序結果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("CLS");/*選擇排序*/void xuanze(int A,int n) int i,j,k,t,l,h=1;for(i=0;i<n-1;i+)k=i;for(j=i+1;j&l

19、t;n;j+)if(Aj<Ak) k=j;if(i!=k)t=Ai;Ai=Ak;Ak=t;printf("第%d趟:",h+);for(l=0;l<n;l+)printf("%d ",Al);printf("n");printf("n排序結果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");printf("n");system("pause");system("C

20、LS");/*冒泡排序*/void maopao(int A,int n) int i,j,t,h=1,p;for(j=0;j<n-1;j+)for(i=0;i<n-1-j;i+)if(Ai>Ai+1)t=Ai,Ai=Ai+1,Ai+1=t,p+;printf("第%d趟:",h+);for(p=0;p<n;p+)printf("%d ",Ap);printf("n");printf("n排序結果:");for(i=0;i<n;i+)printf("%d "

21、;,Ai);printf("n");printf("n");system("pause");system("CLS");/*堆排序*/void shift(int A , int i , int m) int k,t; t=Ai;k=2*i+1; while (k<m) if(k<m-1)&&(Ak<Ak+1) k+; if(t<Ak)Ai=Ak;i=k;k=2*i+1; else break; Ai=t;void duipai(int A , int n) /a 為排序數組

22、，n為數組大小int i,k,h=1,j;for (i=n/2-1;i>=0;i-)shift(A,i,n); for (i=n-1;i>=1;i-)k=A0;A0=Ai;Ai=k;shift(A,0,i);printf("第%d趟:",h+);for(j=0;j<n;j+)printf("%d ",Aj);printf("n");printf("n排序結果:");for(i=0;i<n;i+)printf("%d ",Ai);printf("n");

23、printf("n");system("pause");system("CLS");/*歸并排序*/void merge(int number,int first,int last,int mid) int number_temp10=0; int i=first,j=mid+1,k; for(k=0;k<=last-first;k+) if (i=mid+1) number_tempk=numberj+; continue; if (j=last+1) number_tempk=numberi+; continue; if (

24、numberi<numberj) number_tempk=numberi+; else number_tempk=numberj+; for (i=first,j=0;i<=last;i+,j+) numberi = number_tempj;void merge_sort(int number,int first,int last) int mid=0; if(first<last) mid=(first+last)/2; merge_sort(number,first,mid); merge_sort(number,mid+1,last); merge(number,f

25、irst,last,mid); void guibing(int a,int n)int i;merge_sort(a,0,n-1);printf("n排序結果:");for(i=0;i<n;i+) printf("%d ",ai);printf("n");printf("n");system("pause");system("CLS");/*基數排序*/void jishu(int data,int n)int temp1010=0; int order10=0; i

26、nt i,j,k,q,lsd; k=0; q=1; while(q<=n) for(i=0;i<n;i+) lsd=(datai/q)%n); templsdorderlsd=datai; orderlsd+; for(i=0;i<n;i+) if(orderi != 0) for(j=0;j<orderi;j+) datak=tempij; k+; orderi = 0; q *= n; k = 0; printf("n排序結果:");for(i=0;i<n;i+)printf("%d ",datai);printf("n");printf("n");system("pause");system("CLS"