計算機課程設(shè)計---冒泡排序

1、<p><b>　　課程設(shè)計報告</b></p><p>　　指導(dǎo)者： </p><p>　　評閱者： </p><p>　　2013年 4月</p><p>　作 者:學(xué) 號：<

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

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

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

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

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

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

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

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

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

11、新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。</p><p>　　用二重循環(huán)實現(xiàn)，外循環(huán)變量設(shè)為i，內(nèi)循環(huán)變量設(shè)為j。假如有10個數(shù)需要進行排序，則外循環(huán)重復(fù)9次，內(nèi)循環(huán)依次重復(fù)9，8，...，1次。每次進行比較的兩個元素都是與內(nèi)循環(huán)j有關(guān)的，它們可以分別用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四個數(shù)用冒泡排序方法進行排序。先把四個數(shù)依次存入R[1..4]數(shù)組中，具體排序過程如下圖所示：</p><p><b>　　圖一</b></p><p>　　第一趟結(jié)果：5 2 4 9 最大數(shù)9在R[4]中。</p><p&

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

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

15、gt;</p><p>　　2.3.2 冒泡排序的程序</p><p>　　本程序的編寫采用調(diào)用子函數(shù)的方法，先定義一個子函數(shù)Bubble_Sort(n)實現(xiàn)冒泡排序的功能，在主函數(shù)中輸入要排序的數(shù)字，在調(diào)用子函數(shù)后實現(xiàn)數(shù)字的排序。</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; /*本趟排序前，交換標志應(yīng)為假*/ </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 冒泡排序的調(diào)試</p><p>　　3．1 冒泡排序的調(diào)試方法</p><p>　　本程序采用Microsoft Visual C++

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、7] 陳媛，何波，涂曉江，涂飛。算法與數(shù)據(jù)結(jié)構(gòu)。棧，2005（4）</p><p>　　[8] 張勇，劉君儀。數(shù)據(jù)結(jié)構(gòu)。棧，2006（8）：96～107</p><p>　　[9] 王挺，周會平。c++程序設(shè)計。2005（1）：30～38 </p><p>　　[10]嚴蔚敏，吳偉民。數(shù)據(jù)結(jié)構(gòu)。北京：清華大學(xué)出版社，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; /*本趟排序前，交換標志應(yīng)為假*/ </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()