4.2　冒泡排序算法

冒泡排序（Bubble Sort）算法是所有排序算法中最簡單、最基本的一種。冒泡排序算法的思路就是交換排序，通過相鄰數(shù)據(jù)的交換來達(dá)到排序的目的。

4.2.1　冒泡排序算法

冒泡排序算法通過多次比較和交換來實(shí)現(xiàn)排序，其排序流程如下：

（1）對數(shù)組中的各數(shù)據(jù)，依次比較相鄰的兩個元素的大小。

（2）如果前面的數(shù)據(jù)大于后面的數(shù)據(jù)，就交換這兩個數(shù)據(jù)。經(jīng)過第一輪的多次比較排序后，便可將最小的數(shù)據(jù)排好。

（3）再用同樣的方法把剩下的數(shù)據(jù)逐個進(jìn)行比較，最后便可按照從小到大的順序排好數(shù)組各數(shù)據(jù)。

為了更好地理解冒泡排序算法的執(zhí)行過程，下面舉一個實(shí)際數(shù)據(jù)的例子來一步一步地執(zhí)行冒泡排序算法。對于5個整型數(shù)據(jù)118、101、105、127、112，這是一組無序的數(shù)據(jù)。對其執(zhí)行冒泡排序過程，如圖4-2所示。

冒泡排序算法的執(zhí)行步驟如下：

（1）第1次排序，從數(shù)組的尾部開始向前依次比較。首先是127和112比較，由于127大于112，因此將數(shù)據(jù)112向上移了一位；同理，118和101比較，將數(shù)據(jù)101向前移了一位。此時排序后的數(shù)據(jù)為101、118、105、112、127。

（2）第2次排序，從數(shù)組的尾部開始向前依次比較。105和118比較，可以將數(shù)據(jù)105向前移一位。此時排序后的數(shù)據(jù)為101、105、118、112、127。

（3）第3次排序，從數(shù)組的尾部開始向前依次比較。由于112和118比較，可以將數(shù)據(jù)118向前移一位。此時排序后的數(shù)據(jù)為101、105、112、118、127。

（4）第4次排序時，此時，各個數(shù)據(jù)已經(jīng)按順序排列好，所以無須再進(jìn)行數(shù)據(jù)交換。此時，排序的結(jié)果為101、105、112、118、127。

從上面的例子可以非常直觀地了解到冒泡排序算法的執(zhí)行過程。整個排序過程就像水泡的浮起過程，故因此而得名。冒泡排序算法在對n個數(shù)據(jù)進(jìn)行排序時，無論原數(shù)據(jù)有無順序，都需要進(jìn)行n-1步的中間排序。這種排序方法思路簡單直觀，但是缺點(diǎn)是執(zhí)行的步驟稍長，效率不高。

一種改進(jìn)的方法，即在每次中間排序之后，比較一下數(shù)據(jù)是否已經(jīng)按照順序排列完成。如果排列完成則退出排序過程，否則便繼續(xù)進(jìn)行冒泡排序。這樣，對于數(shù)據(jù)比較有規(guī)則的，可以加速算法的執(zhí)行過程。

冒泡排序算法的示例代碼如下：

在上述代碼中，輸入?yún)?shù)a一般為一個數(shù)組的首地址。待排序的原數(shù)據(jù)便保存在數(shù)組a中，程序中通過兩層循環(huán)來對數(shù)據(jù)進(jìn)行冒泡排序。讀者可以結(jié)合前面的冒泡排序算法加深理解。這里，為了讓讀者清楚排序算法的執(zhí)行過程，在排序的每一步都輸出了當(dāng)前的排序結(jié)果。

4.2.2　冒泡排序算法實(shí)例

學(xué)習(xí)了前面的冒泡排序算法的基本思想和算法之后。下面通過一個完整的例子說明冒泡排序法在整型數(shù)組排序中的應(yīng)用，程序示例如下：

【程序4-1】

在上述代碼中，程序定義了符號常量SIZE，用于表征需要排序整型數(shù)組的大小。在主方法中，首先聲明一個整型數(shù)組，然后對數(shù)組進(jìn)行隨機(jī)初始化，并輸出排序前的數(shù)組內(nèi)容。接著，調(diào)用冒泡排序算法的方法來對數(shù)組進(jìn)行排序。最后，輸出排序后的數(shù)組。

該程序的執(zhí)行結(jié)果，如圖4-3所示。圖中顯示了每一步排序的中間結(jié)果。從中可以看出從第4步之后便已經(jīng)完成對數(shù)據(jù)的排序，但是算法仍然需要進(jìn)行后續(xù)的比較步驟。讀者可以根據(jù)前面介紹的思路，加入判斷部分，使之能夠盡早結(jié)束排序過程，從而提高程序的執(zhí)行效率。