計算機課程設計---冒泡排序

1、<p><b>　　課程設計報告</b></p><p>　　指導者： </p><p>　　評閱者： </p><p>　　2013年 4月</p><p>　作 者:學 號：<

2、;/p><p>　教學點:</p><p>　專 業(yè):機電一體化工程</p><p>　題 目:冒泡排序</p><p>　　課 程 設 計 報 告 摘 要</p><p><b>　　目 次</b></p><p>　　1 引言…………………………………………………

3、…………………………… 1</p><p>　　2 冒泡排序的實現 ………………………………………………………………… 1</p><p>　　2.1 冒泡排序的基本概念 ………………………………………………………… 1</p><p>　　2.2 冒泡排序引例………………………………………………………………… 1</p><p>　　2.

4、3冒泡排序的流程圖及程序代碼………………………………………… 2</p><p>　　3 冒泡排序的調試 ……………………………………………………………………4</p><p>　　3.1 冒泡排序的調試方法 ……………………………………………………………4</p><p>　　3.2 程序調試 …………………………………………………………………………5<

5、;/p><p>　　4 冒泡排序的性能分析 ………………………………………………………………6</p><p>　　4.1 時間復雜度 ………………………………………………………………………6</p><p>　　4.2 空間復雜度 ………………………………………………………………………7</p><p>　　4.3 穩(wěn)定性 ………………

6、……………………………………………………………7</p><p>　　5 冒泡排序的不足 ……………………………………………………………………7</p><p>　　結論 …………………………………………………………………………………… 9</p><p>　　致謝 ……………………………………………………………………………………10</p><

7、;p>　　參考文獻………………………………………………………………………………11</p><p>　　附錄A …………………………………………………………………………… 13</p><p><b>　　1 引言</b></p><p>　　在許多程序設計中，我們需要將一個數列進行排序，以方便統計，而冒泡排序一直由于其簡潔的思想方

8、法而倍受青睞</p><p>　　冒泡排序，是指計算機的一種排序方法，它的時間復雜度為O（n^2），雖然不及堆排序、快速排序，但是有兩個優(yōu)點：1.“編程復雜度”很低，很容易寫出代碼；2.具有穩(wěn)定性，這里的穩(wěn)定性是指原序列中相同元素的相對順序仍然保持到排序后的序列，而堆排序、快速排序均不具有穩(wěn)定性。不過，一路、二路歸并排序、不平衡二叉樹排序的速度均比冒泡排序快，且具有穩(wěn)定性，但速度不及堆排序、快速排序。冒泡排序是經

9、過n-1趟子排序完成的，第i趟子排序從第1個數至第n-i個數，若第i個數比后一個數大（則升序，小則降序）則交換兩數。</p><p>　　因為冒泡排序方法簡單，所以得到廣泛應用。</p><p>　　2 冒泡排序的實現</p><p>　　2．1 冒泡排序的基本概念</p><p>　　冒泡排序的基本概念是：依次比較相鄰的兩個數，將小數放

10、在前面，大數放在后面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放后。然后比較第2個數和第3個數，將小數放前，大數放后，如此繼續(xù)，直至比較最后兩個數，將小數放前，大數放后。至此第一趟結束，將最大的數放到了最后。在第二趟：仍從第一對數開始比較（因為可能由于第2個數和第3個數的交換，使得第1個數不再小于第2個數），將小數放前，大數放后，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個

11、新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。</p><p>　　用二重循環(huán)實現，外循環(huán)變量設為i，內循環(huán)變量設為j。假如有10個數需要進行排序，則外循環(huán)重復9次，內循環(huán)依次重復9，8，...，1次。每次進行比較的兩個元素都是與內循環(huán)j有關的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,9，對于每一個i和j的值依次為1,2,...10-i。<

12、;/p><p>　　2．2 冒泡排序引例</p><p>　　將9,5,2,4四個數用冒泡排序方法進行排序。先把四個數依次存入R[1..4]數組中，具體排序過程如下圖所示：</p><p><b>　　圖一</b></p><p>　　第一趟結果：5 2 4 9 最大數9在R[4]中。</p><p&

13、gt;<b>　　圖二</b></p><p>　　第二趟結果：2 4 5 9 第二大數數5在R[3]。</p><p><b>　　圖三</b></p><p>　　第一趟結果：5 2 4 9 第三大數4在R[2]中.</p><p>　　以上第一趟比較結果出來一個最大數9，發(fā)表放在R[4]中

14、；第二趟出來次大樹5，放在R[3]中，……；四個數進行三趟。其比較過程為相鄰兩數比較，小的浮上去，大的沉下來。</p><p>　　2．3 冒泡排序的流程圖及程序代碼</p><p>　　2.3.1 冒泡排序的流程圖</p><p>　　根據冒泡排序的排序過程可得如下的程序流程圖：</p><p><b>　　圖四</b&

15、gt;</p><p>　　2.3.2 冒泡排序的程序</p><p>　　本程序的編寫采用調用子函數的方法，先定義一個子函數Bubble_Sort(n)實現冒泡排序的功能，在主函數中輸入要排序的數字，在調用子函數后實現數字的排序。</p><p>　　#include <stdio.h></p><p>　　#define M

16、AX 255</p><p>　　#define clrscr()</p><p>　　#define exit</p><p>　　#define getch()</p><p>　　int a[MAX];</p><p>　　void Bubble_Sort(int n)</p><p>　

17、　{ /* a (1..n)是帶排序的文件，采用自下向上掃描，對a做冒泡排序*/</p><p><b>　　int i,j;</b></p><p>　　int exchange; /*交換標志*/</p><p>　　for (i=1;i<n;i++) {/*最多做n-1趟排序*/</p><p>　　ex

18、change=0; /*本趟排序前，交換標志應為假*/ </p><p>　　for(j=n-1;j>=i;j--) /*對當前無序區(qū)a[i..n]自下向上掃描*/</p><p>　　if(a[j+1]<a[j]) {/*交換記錄*/</p><p>　　a[0]=a[j+1]; /*a[0]不是哨兵，僅做暫存單元*/</p>&l

19、t;p>　　a[j+1]=a[j];</p><p>　　a[j]=a[0];</p><p>　　exchange=1; /*發(fā)生了交換，故將交換標志置為真*/</p><p><b>　　}</b></p><p>　　if(!exchange)/*本趟排序未發(fā)生交換，提前終止算法*/</p>&

20、lt;p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>

21、<b>　　int i,n;</b></p><p><b>　　clrscr();</b></p><p>　　puts("Please input total element number of the sequence:");</p><p>　　scanf("%d",&

22、;n);</p><p>　　if(n<=0||n>MAX)</p><p><b>　　{</b></p><p>　　printf("n must more then 0 and less then %d.\n",MAX);</p><p><b>　　exit(0);<

23、;/b></p><p><b>　　}</b></p><p>　　puts("please input the elemengt one by one:");</p><p>　　for(i=1;i<=n;i++)</p><p>　　scanf("%d",&

24、;a[i]);</p><p>　　puts("the sequence you input is:");</p><p>　　for(i=1;i<=n;i++)</p><p>　　printf("%4d",a[i]);</p><p>　　Bubble_Sort(n);</p>

25、<p>　　puts("\nThe sequence after bubble_sort is:");</p><p>　　for(i=1;i<=n;i++)</p><p>　　printf("%4d",a[i]);</p><p>　　puts("\n Press any key to quit…

26、");</p><p><b>　　getch();</b></p><p><b>　　}</b></p><p>　　3 冒泡排序的調試</p><p>　　3．1 冒泡排序的調試方法</p><p>　　本程序采用Microsoft Visual C++

27、6.0調試，首先打開軟件，新建一個C++ source file 文件，輸入文件名稱，選擇合適的文件目錄。如圖所示：</p><p><b>　　圖五</b></p><p>　　新建好文件后，開始編輯程序，然后點擊組建——編譯，如出現錯誤可按F4查找錯誤，修改至無錯誤位置，可有警告。程序檢查無錯誤就可點擊運行程序。</p><p><b

28、>　　圖六</b></p><p><b>　　調試過程</b></p><p>　　按照上面的調試方法運行程序后，首先要輸入的排序數據的總個數。</p><p><b>　　圖七</b></p><p>　　輸入相應的數字（例如 5 ）后顯示的是</p><p

29、><b>　　圖八</b></p><p>　　依次輸入5個數，每隔一個輸入一個空格，待5個數輸入完成后點擊回車確定。第一行顯示的是輸入的順序，第二行顯示的排完順序的一串數字，如輸入2，38,5,47，50五個數。</p><p><b>　　圖九</b></p><p>　　4 冒泡排序的性能分析</p>

30、;<p>　　4．1 時間復雜度</p><p>　　一般情況下冒泡排序的時間復雜度為O（n*n）。但當排序的數完全正序的時候，n個數只進行一趟，比較n-1次，其時間復雜度為O(n)，這是冒泡排序的最好情況。比如將2,4,6,8,10五個數用冒泡排序，只進行一趟，比較四次，不發(fā)生數據交換，排序就結束了。</p><p>　　4．2 空間復雜度</p><

31、;p>　　和直接插入排序一樣，不管有待排序數n有多大，輔助空間只需要一個m，用于兩數交換運算，因此，冒泡排序的空間復雜度也為O（1）。</p><p><b>　　4．2 穩(wěn)定性</b></p><p>　　從程序可以看出，當a[j]>a[j+1]時才交換，若相等則不交換，因此，冒泡排序是穩(wěn)定的排序。</p><p>　　綜上所述

32、，冒泡排序的基本思想是：相鄰關鍵字進行比較，不合適就交換。因為冒泡排序方法簡單，所以得到廣泛應用。</p><p>　　5 冒泡排序的不足</p><p>　　冒泡排序法存在的不足及改進方法：</p><p>　　第一，在排序過程中，執(zhí)行完最后的排序后，雖然數據已全部排序完備，但程序無法判斷是否完成排序，為了解決這一不足，可設置一個標志位flag，將其初始值設置為

33、非0，表示被排序的表是一個無序的表，每一次排序開始前設置flag值為0，在進行數據交換時，修改flag為非0。在新一輪排序開始時，檢查此標志，若此標志為0，表示上一次沒有做過交換數據，則結束排序；否則進行排序；</p><p>　　第二，當排序的數據比較多時排序的時間會明顯延長。</p><p>　　改進方法：快速排序：具體做法：任意選取某一記錄（通常取第一個記錄），比較其關鍵字與所有記錄

34、的關鍵字，并將關鍵字比它小的記錄全部放在它的前面，將比它大的記錄均存放在它的后面，這樣，經過一次排序之后，可將所有記錄以該記錄所在的分界點分為兩部分，然后分別對這兩部分進行快速排序，直至排序完</p><p>　　局部冒泡排序算法對冒泡排序的改進：</p><p>　　在冒泡排序中，一趟掃描有可能無數據交換，也有可能有一次或多次數據交換，在傳統的冒泡排序算法及近年來的一些改進的算法中，只記

35、錄一趟掃描有無數據交換的信息，對數據交換發(fā)生的位置信息則不予處理。為了充分利用這一信息，可以在一趟全局掃描中，對每一反序數據對進行局部冒泡排序處理，稱之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時間復雜度，并且在正序和逆序的情況下，所需的關鍵字的比較次數和移動次數完全相同。由于局部冒泡排序和冒泡排序的數據移動次數總是相同的，而局部冒泡排序所需關鍵字的比較次數常少于冒泡排序，這意味著局部冒泡排序很可能在平均比較次數上對冒泡排序有

36、所改進，當比較次數較少的優(yōu)點不足以抵消其程序復雜度所帶來的額外開銷，而當數據量較大時，局部冒泡排序的時間性能則明顯優(yōu)于冒泡排序。</p><p><b>　　結 論</b></p><p>　　通過了這一次的課程設計，更加詳細的了解了冒泡排序的排序方法，從它最開始的基本概念到流程圖的設計設計，程序的編寫，最后到程序的調試，系統的掌握了冒泡排序的操作以及程序思路。由于

37、幾種排序的方法大同小異，所以在這次課程設計之后，對于其他的幾種排序方法也有了更加深刻的了解。</p><p>　　計算機軟件在現代社會已近得到了最廣泛的利用，對于我們學生來說，掌握必要的計算機軟件基礎知識是必不可少的。學完這門課后我們對計算機軟件基礎料了解了更多的知識，對計算機軟件業(yè)有了更多的了解，這對我們以后的發(fā)展有了很大的幫助。</p><p><b>　　致 謝</

38、b></p><p>　　這篇論文的完成離不開老師和同學的支持，感謝老師的細心指導，在論文的排版上感謝老師的意見，才使得這篇論文排版如此的整齊。在流程圖的繪制以及程序的編寫時，遇到困難難以繼續(xù)，在同學的熱心幫助下，我找到了相應的參考書，在參考書上我發(fā)現了解決困難的方法，才能繼續(xù)書寫論文。也感謝舍友細心的幫我核查，改掉其他的細小毛病。</p><p>　　最后感謝南京理工大學能給我這次

39、機會，讓我學到更多的知識，也感謝蘇州市職業(yè)大學對我的教育和指導。</p><p><b>　　參 考 文 獻</b></p><p>　　[1] 寧正元，王秀麗.算法與數據的結構，2006：29～32</p><p>　　[2] 楊輝.楊輝的縱橫圖論，2003：12～14</p><p>　　[3] 唐王希.太乙金鏡式經

40、，2000：35～37</p><p>　　[4] 王力柱。c/c++與數據結構。棧，2003（8）：142～152</p><p>　　[5] 徐孝凱，賀桂英。數據結構。棧和隊列，2004（10）：76～92</p><p>　　[6] 吳乃陵，李海文。c++程序設計。棧，2003（8）：80～87 ，263～270</p><p>　　[

41、7] 陳媛，何波，涂曉江，涂飛。算法與數據結構。棧，2005（4）</p><p>　　[8] 張勇，劉君儀。數據結構。棧，2006（8）：96～107</p><p>　　[9] 王挺，周會平。c++程序設計。2005（1）：30～38 </p><p>　　[10]嚴蔚敏，吳偉民。數據結構。北京：清華大學出版社，200

42、1</p><p><b>　　附錄A：</b></p><p><b>　　程序代碼：</b></p><p>　　#include <stdio.h></p><p>　　#define MAX 255</p><p>　　#define clrscr()&l

43、t;/p><p>　　#define exit</p><p>　　#define getch()</p><p>　　int a[MAX];</p><p>　　void Bubble_Sort(int n)</p><p>　　{ /* a (1..n)是帶排序的文件，采用自下向上掃描，對R做冒泡排序*/</p&

44、gt;<p><b>　　int i,j;</b></p><p>　　int exchange; /*交換標志*/</p><p>　　for (i=1;i<n;i++) {/*最多做n-1趟排序*/</p><p>　　exchange=0; /*本趟排序前，交換標志應為假*/ </p><p&

45、gt;　　for(j=n-1;j>=i;j--) /*對當前無序區(qū)R[i..n]自下向上掃描*/</p><p>　　if(a[j+1]<a[j]) {/*交換記錄*/</p><p>　　a[0]=a[j+1]; /*R[0]不是哨兵，僅做暫存單元*/</p><p>　　a[j+1]=a[j];</p><p>　　a[j

46、]=a[0];</p><p>　　exchange=1; /*發(fā)生了交換，故將交換標志置為真*/</p><p><b>　　}</b></p><p>　　if(!exchange)/*本趟排序未發(fā)生交換，提前終止算法*/</p><p><b>　　return;</b></p>

47、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int i,n;</b></p><p&

48、gt;<b>　　clrscr();</b></p><p>　　puts("Please input total element number of the sequence:");</p><p>　　scanf("%d",&n);</p><p>　　if(n<=0||n>MAX

49、)</p><p><b>　　{</b></p><p>　　printf("n must more then 0 and less then %d.\n",MAX);</p><p><b>　　exit(0);</b></p><p><b>　　}</b&

50、gt;</p><p>　　puts("please input the elemengt one by one:");</p><p>　　for(i=1;i<=n;i++)</p><p>　　scanf("%d",&a[i]);</p><p>　　puts("the se

51、quence you input is:");</p><p>　　for(i=1;i<=n;i++)</p><p>　　printf("%4d",a[i]);</p><p>　　Bubble_Sort(n);</p><p>　　puts("\nThe sequence after bubb

52、le_sort is:");</p><p>　　for(i=1;i<=n;i++)</p><p>　　printf("%4d",a[i]);</p><p>　　puts("\n Press any key to quit…");</p><p><b>　　getch()