武漢理工大學-《數(shù)據(jù)結構》課程論文-中國好學長系列之小灰灰的爸爸

1、附件1：學 號： 課 程 設 計題 目交換排序的設計與實現(xiàn)學 院計算機科學與技術學院專 業(yè)軟件工程專業(yè)班 級中國好學長系列姓 名小灰灰的爸爸指導教師夏紅霞2013年元月25日課程設計任務書學生姓名： 專業(yè)班級： 指導教師： 夏紅霞 工作單位：計算機科學與技術學院 題 目: 交換排序的設計與實現(xiàn)初始條件：理論：學習了數(shù)據(jù)結構課程，掌握了基本的數(shù)據(jù)結構和常用的算法；實踐：軟件工程系實驗室提供計算機及軟件開發(fā)環(huán)境。要求完成的主要任務: （包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）1、系統(tǒng)應具備的功能：（1）隨機產(chǎn)生1000個整數(shù)（2）實現(xiàn)冒泡排序、雙向冒泡排序和快速排序（3）比較各種

2、交換排序的優(yōu)劣2、數(shù)據(jù)結構設計；3、主要算法設計；4、編程及上機實現(xiàn)；5、撰寫課程設計報告，包括：（1）設計題目；（2）摘要和關鍵字（中文和英文）；（3）正文，包括引言、需求分析、數(shù)據(jù)結構設計、算法設計、程序?qū)崿F(xiàn)及測試、設計體會等；（4）結束語；（5）參考文獻。時間安排： 2013年元月21日25日 （第21周） 元月21日 查閱資料元月22日 系統(tǒng)設計，數(shù)據(jù)結構設計，算法設計元月23日-24日 編程并上機調(diào)試，驗收程序元月25日 撰寫報告、提交報告 指導教師簽名： 2013年元月21日系主任（或責任教師）簽名： 2013年元月21日交換排序的設計與實現(xiàn)摘要：設計一個程序，要求能夠產(chǎn)生1000

3、個隨機數(shù)，分別用冒泡排序、雙向冒泡排序和快速排序三種方法對它們進行排序并比較各種交換排序法的優(yōu)劣。關鍵字： 隨機數(shù) 交換排序 數(shù)據(jù)結構 算法 abstract：Design a program, can generate 1000 random numbers, respectively using bubble sort, bidirectional bubble sort and quick sort of three methods to sort them out and compared the pros and cons of various exchange sort.Keywo

4、rds：Random numbers Exchange sort Data structure Algorithm1引言1.1冒泡排序法首先將第一個關鍵字和第二個關鍵字進行比較，若為逆序，則將兩關鍵字交換，然后比較第二個和第三個關鍵字，依此類推，直至第n-1個和第n個關鍵字相比較，結果使最大的關鍵字被安置到最后一個位置上，此為一趟起泡排序。然后開始第二趟起泡排序，其結果是將次大的關鍵字被安置到第n-1個位置上，以此類推，直至序列有序。1.2雙向冒泡排序法雙向冒泡排序法是在冒泡排序法的基礎上改進的，首先它在將最大關鍵字安置在最后一個位置上后也將最小關鍵字安置在第一個位置，然后開始第二趟起泡排序，

5、以此類推直至序列有序，由于它讓序列的兩個方向同時進行排序，故稱雙向冒泡排序。1.3快速排序法快速排序法是一種效率很高的排序方法，適用于排序問題的規(guī)模很大但對于穩(wěn)定性不作要求的情況。它的設計方法是分治法，基本思想是：在待排序列中選擇一個對象作為樞軸，然后進行一趟快速排序，將序列分割為兩個子序列，一個子序列的所有對象都不大于樞軸，一個都不小于樞軸。然后便對這兩序列重復上面的操作，依此類推，直至所有對象都被確定了位置，即序列有序。2 需求分析本系統(tǒng)應具有三個功能：產(chǎn)生隨機整數(shù)，對關鍵字進行排序和記錄排序所比較和調(diào)換的次數(shù)。2.1產(chǎn)生隨機數(shù)產(chǎn)生隨機數(shù) 系統(tǒng)要求產(chǎn)生1000個整數(shù)，故采用隨機函數(shù)rand

6、來實現(xiàn)，在主函數(shù)頭文件中包含time.h和stdlib.h。系統(tǒng)中采用srand函數(shù)來對隨機函數(shù)rand進行初始化，產(chǎn)生的隨機數(shù)用一維數(shù)組來存儲。2.2對關鍵字排序用冒泡排序法、雙向冒泡排序法和快速排序法分別對關鍵字排序 2.3比較三種交換排序的優(yōu)劣本實驗要求比較三種交換排序的優(yōu)劣，其主要評判標準是時間復雜度。數(shù)據(jù)結構中理論的分析了它們排序所用時間，而此實驗用具體數(shù)據(jù)論證。3 數(shù)據(jù)結構設計3.1流程圖3.2 算法設計3.2.1產(chǎn)生1000個隨機數(shù)srand(time(NULL); /隨機產(chǎn)生1000個1000以內(nèi)的正整數(shù) printf(隨機產(chǎn)生1000個整數(shù)n); for(int i=0;i1

7、000;i+) ai=rand()%1000; /保證產(chǎn)生的整數(shù)在1000內(nèi)，并存于數(shù)組a printf(%d ,ai); for(m=0;m1000;m+) bm=am; /將數(shù)組a復制到數(shù)組b,ccm=am; 3.2.2冒泡排序 對于n個關鍵字的起泡排序，共要進行n-1趟的排序，第i趟要對n-i+1個關鍵字進行排序，即key0到keyn-i，可知共有兩層循環(huán)。在每一次的排序中，都定義一個臨時變量temp，用以作為關鍵字交換時的臨時存儲單元。Void bubble_sort(int array) /冒泡排序法排列1000個數(shù)并記錄比較和調(diào)換次數(shù) int temp,i,j;int m=0,p=

8、0;for(j=0;j999;j+)for(i=0;iarrayi+1)temp=arrayi;arrayi=arrayi+1;arrayi+1=temp;+m; +p; printf(冒泡排序結果:n); for(j=0;j1000;j+)printf(%d ,arrayj);printf(n);3.2.3記錄冒泡排序法的對調(diào)次數(shù)與比較次數(shù)printf(n*n);printf(nntt冒泡排序的對調(diào)次數(shù)：%d nn,m);printf(tt冒泡排序的比較次數(shù)：%d nn,p);3.2.4雙向冒泡排序 對于n個關鍵字的冒泡排序，共要進行n-1趟的排序，第i趟要對n-i+1個關鍵字進行排序，即k

9、ey0到keyn-i，且每次正向排序后馬上反向排序，可知共有兩層循環(huán)。在每一次的排序中，都定義一個臨時變量t，用以作為關鍵字交換時的臨時存儲單元。void maopao(int source,int n) /雙向冒泡排序法排列1000個數(shù)并記錄比較和調(diào)換次數(shù) int start=0,end=n-1; int i,k=0,l=0; while(start=end)/*如果還有元素沒有確定其位置*/ for(i=start;isourcei+1) int t; t=sourcei; sourcei=sourcei+1; sourcei+1=t; +k; +l; end-;/*找到最大數(shù)*/ for

10、(i=end;istart;i-)/*尋找剩余元素的最小元素*/ if(sourceisourcei-1) int t; t=sourcei; sourcei=sourcei-1; sourcei-1=t; +k; +l; start+;/*找到一個最小數(shù)*/ printf(雙向冒泡排序結果:n); for(int j=0;j1000;j+) printf(%d ,sourcej); printf(n);3.2.5記錄雙向冒泡排序法的對調(diào)次數(shù)與比較次數(shù)printf(n*n);printf(nntt雙向冒泡排序的對調(diào)次數(shù)：%dnn,k);printf(tt雙向冒泡排序的比較次數(shù)：%dnn,l);

11、3.2.6快速排序快速排序中需要選取一個樞軸，樞軸不需要隨著關鍵字移動，故可將它暫寄在temp，還需要定義兩個指針l和r。排序分兩個函數(shù)實現(xiàn)，一個是遞歸形式的快速排序，另一個是一趟快速排序。在對由樞軸分割的子序列進行排序時，依賴于前者對后者的調(diào)用來實現(xiàn)，后者完成具體的排序過程。void q_sort(int R, int l, int r,int &a,int &b) /快速排序法排列1000個數(shù)并記錄比較和調(diào)換次數(shù) int temp;int i=l,j=r;if(li&Rjtemp) -j;if(ij) Ri=Rj; +i; +a; +b; while(ij&Ritemp) +i; if(i

12、j)Rj=Ri;-j;+a; +b;Ri=temp;q_sort(R,l,i-1,a,b);q_sort(R,i+1,r,a,b);printf(快速排序結果:n); for(int j=0;j1000;j+) printf(%d ,cj); printf(n);3.2.7記錄快速排序法的對調(diào)次數(shù)與比較次數(shù)printf(n*n);printf(nntt快速排序的對調(diào)次數(shù)：%dnn,change);printf(tt快速排序的比較次數(shù)：%dnn,compare); 4 程序?qū)崿F(xiàn)及測試4.1源代碼#include #include #include void bubble_sort(int arr

13、ay) int temp,i,j;int m=0,p=0;for(j=0;j999;j+)for(i=0;iarrayi+1)temp=arrayi;arrayi=arrayi+1;arrayi+1=temp;+m; +p; printf(冒泡排序結果:n); for(j=0;j1000;j+)printf(%d ,arrayj);printf(n);printf(n*n);printf(nntt冒泡排序的對調(diào)次數(shù)：%d nn,m);printf(tt冒泡排序的比較次數(shù)：%d nn,p); void maopao(int source,int n) int start=0,end=n-1; i

14、nt i,k=0,l=0; while(start=end)/*如果還有元素沒有確定其位置*/ for(i=start;isourcei+1) int t; t=sourcei; sourcei=sourcei+1; sourcei+1=t; +k; +l; end-;/*找到最大數(shù)*/ for(i=end;istart;i-)/*尋找剩余元素的最小元素*/ if(sourceisourcei-1) int t; t=sourcei; sourcei=sourcei-1; sourcei-1=t; +k; +l; start+;/*找到一個最小數(shù)*/ printf(雙向冒泡排序結果:n); f

15、or(int j=0;j1000;j+) printf(%d ,sourcej); printf(n); printf(n*n);printf(nntt雙向冒泡排序的對調(diào)次數(shù)：%dnn,k);printf(tt雙向冒泡排序的比較次數(shù)：%dnn,l); void q_sort(int R, int l, int r,int &a,int &b) int temp;int i=l,j=r;if(li&Rjtemp) -j;if(ij) Ri=Rj; +i; +a; +b; while(ij&Ritemp) +i; if(ij)Rj=Ri;-j;+a; +b;Ri=temp;q_sort(R,l,i

16、-1,a,b);q_sort(R,i+1,r,a,b); int main(void) int a1000,b1000,c1000; int change=0,compare=0; int m; srand(time(NULL); printf(隨機產(chǎn)生1000個整數(shù)n); for(int i=0;i1000;i+) ai=rand()%1000; printf(%d ,ai); for(m=0;m1000;m+) bm=am;cm=am; printf(nn*nn); bubble_sort(a); maopao(b,1000); q_sort(c,0, 999,change,compare

17、); printf(快速排序結果:n); for(int j=0;j1000;j+) printf(%d ,cj); printf(n);printf(n*n);printf(nntt快速排序的對調(diào)次數(shù)：%dnn,change);printf(tt快速排序的比較次數(shù)：%dnn,compare); return 0; 4.2運行結果產(chǎn)生1000個隨機數(shù)冒泡排序的結果冒泡排序的理論比較次數(shù)為n（n-1）/2=1000*(1000-1)/2=499500這與運行得出的實際值相符合雙向冒泡排序的理論比較次數(shù)為n（n-1）/2=1000*(1000-1)/2=499500這與運行得出的實際值相符合快速排

18、序法的理論比較次數(shù)為n(log(2)n)/2=1000*log(2)1000/2=4985這與實際運行得出的值相近比較三種排序方法可知，冒泡排序和雙向冒泡排序的調(diào)換次數(shù)和比較次數(shù)是一樣的，而快速排序法則明顯優(yōu)于其他兩種交換排序方法，其效率約為前兩者的100倍。本程序由于所要排序的數(shù)較多，要用到隨機函數(shù)，產(chǎn)生足夠多的隨機數(shù)；要比較兩種交換排序的優(yōu)劣，則要記錄各種排序法所比較和調(diào)換的次數(shù)以便比較。5設計體會這個程序的設計看似簡單，但實際操作起來卻很麻煩，編出的程序常常無法運行，且很難找出錯誤，修改了很多次才能正常運行，由于這次的課程設計，我更加體會到了要將理論運用于實踐是有難度的，以后要多多上機編寫程序而不能總是理論上明白就行。