冒泡排序及其改進算法的教學設計與實現

曹春梅　宋潔

摘 要：在C語言程序設計中，排序算法是使用頻率最高的算法之一，而冒泡排序是其中一種典型且相對簡單的方法，學習它是為后面的選擇排序作鋪墊。文章在最初的冒泡排序算法上改進了兩次，使算法達到一個更好的效果。通過冒泡排序及其改進算法的學習，可以提高學生的程序設計能力，為今后在算法與程序設計方面的進一步研究和學習打下基礎。

關鍵詞：C語言；排序算法；冒泡排序；改進算法；程序設計能力

1 冒泡排序算法

1.1 導入

首先可以通過生活中常見的例子來引出問題。由圖1提出問題：如何將這6支長短不一的鉛筆進行由短到長的排序？

經過討論，發現排序方法有很多種，本文主要介紹其中一種—冒泡排序法[1-3]。

為了對冒泡排序有直觀的了解，我們通過Flash動畫[4-5]演示排序過程：在每一趟的排序中，將鉛筆兩兩比較，較長的鉛筆移至后面。通過第一趟排序，最長的鉛筆移至最后面。依次類推，第二趟排序后，第二長的鉛筆移至倒數第二的位置；第三趟排序后，第三長的鉛筆移至倒數第三的位置；第四趟排序后，第四長的鉛筆移至倒數第四的位置；第五趟排序后，第五長的鉛筆移至倒數第五的位置，剩下的那支鉛筆必然是最短的，而且排在第一的位置。

1.2 典型例子分析

為了更好地理解算法，我們通過一個典型例子來分析：用冒泡排序的方法將一組無序數據72，34，61，93，45，9排成從小到大的順序。

為了方便分析，我們把所給的數據先用一個表格列出來，如表1所示。

按照冒泡排序算法，對這些數據進行由小到大的排序：在每一趟排序中，將數字兩兩比較，若較大數在前，較小數在后，則將兩個數交換位置，否則，兩數位置不變。經過第一趟排序后，最大數93沉到最底。依次類推，第二趟排序后，第二大數72沉到倒數第二個位置；第三趟排序后，第三大數61沉到倒數第三個位置；第四趟排序后，第四大數45沉到倒數第四個位置；第五趟排序后，第五大數34沉到倒數第5個位置，最小數9就理所當然地在第一個位置。

1.3 算法原理

由典型例子的分析可知，在每趟排序過程中，所有數字都要進行兩兩比較，找出相應的最大值，并依次排好順序。

由此，冒泡排序的原理是：對原始數據按從前往后的方向進行多次掃描，每次掃描稱為一趟。當發現相鄰兩個數據的次序與排序要求的大小次序不符合時，即將這兩個數據進行互換。這樣，較小的數據就會逐個向前或向后移動。

1.4 算法設計

1.4.1 數據的輸入

定義一個一維數組a，存儲72，34，61，93，45和9。并且定義兩個表示循環中的趟數、次數的變量，以及一個用來暫時存儲數值的變量。

1.4.2 數據的輸出

通過for語句for（i=0； i<6； i++ ），讓循環執行6次，輸出6個數據。

1.4.3 每一趟比較程序設計

通過for語句for（i=0； i<5； i++ ），讓循環執行5次，也就是讓數組中的數據兩兩比較，若前一個數據大于后一個數據，就會發生交換。

1.4.4 趟數控制的程序設計

在內層for語句的外側加上一層for語句for（j=0； j<5； j++），讓循環執行5次，也就是說比較5趟。

根據這4個步驟，可得冒泡排序的代碼為：

void main（）

{

int a[6]={72，34，61，93，45，9}；

int t， i ， j ；

for（j=0； j<5； j++）

{

for（i=0； i<5； i++）

{

if（a[i]>a[i+1]）

{ t=a[i]； a[i]=a[i+1]； a[i+1]=t；}

}

}

for（i=0； i<6； i++）

print f（“%d”， a[i]）；

}

1.5 思考題

從典型例子分析和算法設計可以看出，每一趟的比較都是a[0]和a[1]比較，a[1]和a[2]比較，a[2]和a[3]比較，a[3]和a[4]比較，a[4]和a[5]比較，過程比較繁瑣，而且效率低下，能否對算法進行優化呢？

1.6 小結

方法總結：n個數排序，從前往后，比較相鄰的兩個數，前大后小，則交換，否則，不交換；該過程需要重復（n-1）趟。

算法總結：循環語句兩兩比較；條件語句判別大小；賦值語句用來交換。

2 冒泡排序之改進算法

2.1 回顧舊知

本文之前的章節中講述了最初的冒泡排序算法[6-8]。其中，每趟排序中數據比較的次數是相同的，現在的重點是將每趟排序中的比較次數優化，使算法效率有所提高。

2.2 引入新知

在上一章的典型例子分析中，首先觀察第一趟與第二趟排序結束后的數據，可以看到第一趟排序后最大值93排到最后，在第二趟排序中，其實無需將其他數值與最后一個值比較，這樣比較次數就可以少一次。在第三趟排序中，其實無需將其他數值與最后一個值、倒數第二個值比較，這樣比較次數就可以少兩次。后面的依次類推。最后可以得到一個結論，對n個數排序，在第j趟排序中只需進行（n-j）次兩兩比較。

2.3 動畫演示

為了更好地理解改進算法，我們通過Flash動畫演示排序過程。

第一趟排序和未改進的算法一樣，兩兩比較，排序完成后93位于最后位置。根據改進算法的描述，第二趟排序時其他柱體無需與已排在最后的柱體比較，所以會少一次比較，只需進行4次比較。依次類推，第三趟排序需進行3次比較；第四趟排序需進行2次比較；第五趟排序進行1次比較即可。

這個動畫可以進一步驗證這次改進算法的正確性。對n個數排序，在第j趟排序中只需進行（n-j）次兩兩比較，可以適當提高算法效率。

2.4 改進算法

在改進算法中，數據輸入、數據輸出、排序趟數和原算法不變，所以不再贅述。在改進算法中有所改變的是每一趟比較程序設計環節：通過for語句for（i=0； i<5-j； i++）實現各次比較，每次的比較都是前后數據兩兩比較，若前一個數據大于后一個數據，就會發生交換，否則，不交換。

根據改進算法得到的代碼為：

void main（）

{

int a[6]={72，34，61，93，45，9}；

int t， i ， j ；

for（j=0；j<5；j++）

{

for（i=0； i<5-j； i++）

{

if（a[i]>a[i+1]）

{ t=a[i]； a[i]=a[i+1]； a[i+1]=t；}

}

}

for（i=0；i<6；i++）

printf（“%d”， a[i]）；

}

2.5 思考題

在這次的改進算法中，對每趟排序中的比較次數進行了優化，使效率有所提高。現在我們思考一個問題，如果n個元素排序，不到（n-1）趟時，已經有序，還需要進行后續的排序嗎？

2.6 小結

使用改進的冒泡排序算法對n個數進行由小到大的排序，需要進行（n-1）趟排序，在第j趟排序中，只需進行（n-j）次兩兩比較。

3 冒泡排序之再改進算法

3.1 回顧舊知

在冒泡排序的改進算法中，我們將內層循環中的i<5改為i<（5-j），使其當前一輪比較確定一個最大的數據后，下一輪該數就不再參與比較。現在考慮的是對于不同的數值排序，排序趟數能否不一樣，是不是可以在這方面進行優化。

3.2 引入新知

比如現在有n個元素需要進行排序，但是不到（n-1）趟時，已經有序了，我們就可以提前終止比較。這次改進算法的關鍵是要加入flag變量作為程序的交換標志。

3.3 改進算法

為了更好地描述改進算法，我們舉例說明：用冒泡排序的方法將一組無序數據19，25，10，45，36排成從小到大的順序。

外層循環和內層循環的整體設計和之前改進的冒泡排序算法一致，不同的是需要在外層循環的內部，且位于內層循環的外部加入一個flag標志，讓其初始值為0。在內層循環中，若在某次比較中有數據交換了位置，就將flag的值改為1；若沒交換，flag值就不變。一趟排序之后，判斷flag是否為0，如果為0，意味著所有數據已經有序，后面無需再交換，就可以跳出循環，比較終止。否則，繼續排序。

根據這進一步的改進，得到的代碼為：

void main（）

{

int a[5]={19，25，10，45，36}；

int t， i ， j ；

for（j=0； j<4； j++）

{

flag=0；

for（i=0；i<4-j；i++）

{

if（a[i]>a[i+1]）

{

flag=1；

t=a[i]； a[i]=a[i+1]； a[i+1]=t；

}

}

if（flag==0） break；

}

for（i=0； i<5；i++）

printf（“%d”， a[i]）；

}

3.4 思考題

之前介紹的算法設計都是通過尋找最大值的方法來實現的，我們可以思考這樣一個問題，如何采用每一輪比較尋找最小值的方法實現冒泡排序的算法設計。

3.5 小結

使用再改進的冒泡排序算法對n個數進行由小到大的排序，在其中加入flag標志，并設置一個初值，若在某趟排序中flag值未發生改變，表明數據已有序，無需進行后續的排序。

4 結語

本文介紹了冒泡排序及其兩種改進算法的教學設計與實現。由最初的排序算法到后來的兩種改進，采取循序漸進的方法，這樣更有助于學生的理解，能讓他們更好地掌握。

[參考文獻]

[1]李坤，鄧波.冒泡排序算法的分析與改進[J].科技信息，2010（22）：216.

[2]程妮.C語言中冒泡排序算法的教學設計與分析[J].現代計算機（專業版），2016（10）：59-63.

[3]劉培元.C語言中冒泡排序算法的分層次學習[J].電腦知識與技術，2013（35）：7987-7989.

[4]劉卉媚. Flash動畫制作技巧[J].才智，2012（23）：199.

[5]蘇也惠. FLASH動畫在新媒體中的應用研究[J].藝術科技，2015（9）：295.

[6]RAMIN E，ARMIN E，TAYEBEH M.A sort implementation comparing with bubble sort and selection sort[C].Shanghai：2011 3rd International Conference on Computer Research and Development，2011：380-381.

[7]HADI S.Multimedia based instructional development：Bubble sort visualization[C].Beijing：2015 6th IEEE International Conference on Software Engineering and Service Science（ICSESS），2015：791-794.

[8]YUNXIA R，SHIYING W. Diagnosability of bubble-sort graph networks under the comparison diagnosis model[C].Jabalpur：2015 International Conference on Computational Intelligence and Communication Networks（CICN），2015：823-826.