曹春梅　宋潔

摘 要：在C語(yǔ)言程序設(shè)計(jì)中，排序算法是使用頻率最高的算法之一，而冒泡排序是其中一種典型且相對(duì)簡(jiǎn)單的方法，學(xué)習(xí)它是為后面的選擇排序作鋪墊。文章在最初的冒泡排序算法上改進(jìn)了兩次，使算法達(dá)到一個(gè)更好的效果。通過(guò)冒泡排序及其改進(jìn)算法的學(xué)習(xí)，可以提高學(xué)生的程序設(shè)計(jì)能力，為今后在算法與程序設(shè)計(jì)方面的進(jìn)一步研究和學(xué)習(xí)打下基礎(chǔ)。

關(guān)鍵詞：C語(yǔ)言；排序算法；冒泡排序；改進(jìn)算法；程序設(shè)計(jì)能力

1 冒泡排序算法

1.1 導(dǎo)入

首先可以通過(guò)生活中常見(jiàn)的例子來(lái)引出問(wèn)題。由圖1提出問(wèn)題：如何將這6支長(zhǎng)短不一的鉛筆進(jìn)行由短到長(zhǎng)的排序？

經(jīng)過(guò)討論，發(fā)現(xiàn)排序方法有很多種，本文主要介紹其中一種—冒泡排序法[1-3]。

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

1.2 典型例子分析

為了更好地理解算法，我們通過(guò)一個(gè)典型例子來(lái)分析：用冒泡排序的方法將一組無(wú)序數(shù)據(jù)72，34，61，93，45，9排成從小到大的順序。

為了方便分析，我們把所給的數(shù)據(jù)先用一個(gè)表格列出來(lái)，如表1所示。

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

1.3 算法原理

由典型例子的分析可知，在每趟排序過(guò)程中，所有數(shù)字都要進(jìn)行兩兩比較，找出相應(yīng)的最大值，并依次排好順序。

由此，冒泡排序的原理是：對(duì)原始數(shù)據(jù)按從前往后的方向進(jìn)行多次掃描，每次掃描稱為一趟。當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排序要求的大小次序不符合時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會(huì)逐個(gè)向前或向后移動(dòng)。

1.4 算法設(shè)計(jì)

1.4.1 數(shù)據(jù)的輸入

定義一個(gè)一維數(shù)組a，存儲(chǔ)72，34，61，93，45和9。并且定義兩個(gè)表示循環(huán)中的趟數(shù)、次數(shù)的變量，以及一個(gè)用來(lái)暫時(shí)存儲(chǔ)數(shù)值的變量。

1.4.2 數(shù)據(jù)的輸出

通過(guò)for語(yǔ)句for（i=0； i<6； i++ ），讓循環(huán)執(zhí)行6次，輸出6個(gè)數(shù)據(jù)。

1.4.3 每一趟比較程序設(shè)計(jì)

通過(guò)for語(yǔ)句for（i=0； i<5； i++ ），讓循環(huán)執(zhí)行5次，也就是讓數(shù)組中的數(shù)據(jù)兩兩比較，若前一個(gè)數(shù)據(jù)大于后一個(gè)數(shù)據(jù)，就會(huì)發(fā)生交換。

1.4.4 趟數(shù)控制的程序設(shè)計(jì)

在內(nèi)層for語(yǔ)句的外側(cè)加上一層for語(yǔ)句for（j=0； j<5； j++），讓循環(huán)執(zhí)行5次，也就是說(shuō)比較5趟。

根據(jù)這4個(gè)步驟，可得冒泡排序的代碼為：

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 思考題

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

1.6 小結(jié)

方法總結(jié)：n個(gè)數(shù)排序，從前往后，比較相鄰的兩個(gè)數(shù)，前大后小，則交換，否則，不交換；該過(guò)程需要重復(fù)（n-1）趟。

算法總結(jié)：循環(huán)語(yǔ)句兩兩比較；條件語(yǔ)句判別大小；賦值語(yǔ)句用來(lái)交換。

2 冒泡排序之改進(jìn)算法

2.1 回顧舊知

本文之前的章節(jié)中講述了最初的冒泡排序算法[6-8]。其中，每趟排序中數(shù)據(jù)比較的次數(shù)是相同的，現(xiàn)在的重點(diǎn)是將每趟排序中的比較次數(shù)優(yōu)化，使算法效率有所提高。

2.2 引入新知

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

2.3 動(dòng)畫演示

為了更好地理解改進(jìn)算法，我們通過(guò)Flash動(dòng)畫演示排序過(guò)程。

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

這個(gè)動(dòng)畫可以進(jìn)一步驗(yàn)證這次改進(jìn)算法的正確性。對(duì)n個(gè)數(shù)排序，在第j趟排序中只需進(jìn)行（n-j）次兩兩比較，可以適當(dāng)提高算法效率。

2.4 改進(jìn)算法

在改進(jìn)算法中，數(shù)據(jù)輸入、數(shù)據(jù)輸出、排序趟數(shù)和原算法不變，所以不再贅述。在改進(jìn)算法中有所改變的是每一趟比較程序設(shè)計(jì)環(huán)節(jié)：通過(guò)for語(yǔ)句for（i=0； i<5-j； i++）實(shí)現(xiàn)各次比較，每次的比較都是前后數(shù)據(jù)兩兩比較，若前一個(gè)數(shù)據(jù)大于后一個(gè)數(shù)據(jù)，就會(huì)發(fā)生交換，否則，不交換。

根據(jù)改進(jìn)算法得到的代碼為：

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 思考題

在這次的改進(jìn)算法中，對(duì)每趟排序中的比較次數(shù)進(jìn)行了優(yōu)化，使效率有所提高?，F(xiàn)在我們思考一個(gè)問(wèn)題，如果n個(gè)元素排序，不到（n-1）趟時(shí)，已經(jīng)有序，還需要進(jìn)行后續(xù)的排序嗎？

2.6 小結(jié)

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

3 冒泡排序之再改進(jìn)算法

3.1 回顧舊知

在冒泡排序的改進(jìn)算法中，我們將內(nèi)層循環(huán)中的i<5改為i<（5-j），使其當(dāng)前一輪比較確定一個(gè)最大的數(shù)據(jù)后，下一輪該數(shù)就不再參與比較?，F(xiàn)在考慮的是對(duì)于不同的數(shù)值排序，排序趟數(shù)能否不一樣，是不是可以在這方面進(jìn)行優(yōu)化。

3.2 引入新知

比如現(xiàn)在有n個(gè)元素需要進(jìn)行排序，但是不到（n-1）趟時(shí)，已經(jīng)有序了，我們就可以提前終止比較。這次改進(jìn)算法的關(guān)鍵是要加入flag變量作為程序的交換標(biāo)志。

3.3 改進(jìn)算法

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

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

根據(jù)這進(jìn)一步的改進(jìn)，得到的代碼為：

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 思考題

之前介紹的算法設(shè)計(jì)都是通過(guò)尋找最大值的方法來(lái)實(shí)現(xiàn)的，我們可以思考這樣一個(gè)問(wèn)題，如何采用每一輪比較尋找最小值的方法實(shí)現(xiàn)冒泡排序的算法設(shè)計(jì)。

3.5 小結(jié)

使用再改進(jìn)的冒泡排序算法對(duì)n個(gè)數(shù)進(jìn)行由小到大的排序，在其中加入flag標(biāo)志，并設(shè)置一個(gè)初值，若在某趟排序中flag值未發(fā)生改變，表明數(shù)據(jù)已有序，無(wú)需進(jìn)行后續(xù)的排序。

4 結(jié)語(yǔ)

本文介紹了冒泡排序及其兩種改進(jìn)算法的教學(xué)設(shè)計(jì)與實(shí)現(xiàn)。由最初的排序算法到后來(lái)的兩種改進(jìn)，采取循序漸進(jìn)的方法，這樣更有助于學(xué)生的理解，能讓他們更好地掌握。

[參考文獻(xiàn)]

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

[2]程妮.C語(yǔ)言中冒泡排序算法的教學(xué)設(shè)計(jì)與分析[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2016（10）：59-63.

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

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

[5]蘇也惠. FLASH動(dòng)畫在新媒體中的應(yīng)用研究[J].藝術(shù)科技，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.