4.2　冒泡排序算法

冒泡排序法是模仿水中氣泡上浮過程而創造的排序方法。以遞增排序為例，其基本思想是：從第一個數開始，依次比較相鄰的兩個數，將小數放在前面，大數放在后面，經過一輪比較后，最大的數將位于最后一個位置。然后繼續從第一個數開始，依次比較相鄰數，直到將倒數第二大的數置于倒數第二位置。如此重復，直到所有數都完成排序。這個過程就好像一個個氣泡逐漸從水底浮到了水面上。

例如，有這樣一組數據：56, 20, 84, 66, 13，如圖4.9所示。按照遞增順序進行排序，步驟如下。

（1）第一次排序。首先用第一個位置的56與第二個位置的20進行比較，因為56大于20，所以進行交換；然后再用第二個位置的56與第三個位置的84進行比較，因為56小于84，所以不用交換；再用第三個位置的84與第四個位置的66進行比較，因為84大于66，所以進行交換；最后用第四個位置84與第五個位置13進行比較，因為84大于13，所以進行交換。這樣就完成了第一次排序，排序過程如圖4.10所示。

經過第一次排序，最大值84被放在了最后的位置。因此在第二次排序時，只需要從第一個數開始，比較到倒數第二個數，也就是13即可。

為了便于表述，將前面未完成排序的數列稱為新數列。后續的相鄰數比較將在此數列中進行。

（2）第二次排序。依然從第一個位置開始比較，即20與56比較，20小于56，不用交換位置；然后56與66比較，56小于66，不用交換位置；最后66與13比較，66大于13，交換位置。這樣就完成了第二次排序，排序過程如圖4.11所示。

經過第二次排序，已經將新數列（20, 56, 66, 13）中的最大值66，也就是原數列的第二大值，放在了倒數第二的位置。因此，在進行第三次排序時，只需要從第一個數開始，比較到倒數第三個數，也就是13即可。

（3）第三次排序。依然從第一個位置開始比較，即20與56比較，20小于56，不用交換位置；再用56與13比較，56大于13，交換位置。這樣就完成了第三次排序，排序過程如圖4.12所示。

經過第三次排序，已經將新數列（20, 56, 13）中的最大值56，也就是原數列的第三大值，放在了倒數第三的位置。因此，在進行第四次排序時，只需要從第一個數開始，比較到13即可。

（4）第四次排序。依然從第一個位置開始比較，即20與13比較，20大于13，交換位置。因為只有兩個數，第四次排序完成。

（5）第五次排序。此時新數列中只剩下13，13小于20，表明已經是最小的數了。至此，整個冒泡排序完成。第四、五次排序過程如圖4.13所示。

接下來用Python代碼實現上述冒泡排序算法。

【實例4.3】　使用冒泡排序法將列表中的數字遞增排序。（實例位置：資源包\Code\04\03）

用Python代碼實現上方示例中的冒泡排序算法，具體代碼如下：

運行結果如圖4.14所示，排序的步驟和上述介紹的冒泡排序法步驟完全吻合。

【實例4.4】　黃金檔各綜藝節目收視率排名。（實例位置：資源包\Code\04\04）

如今各電視臺在周五的黃金檔都會有獨播的綜藝節目。例如，某周的電視臺黃金檔綜藝節目收視率數據如下：14、27、28、10、21，用冒泡排序法把此收視率按照從高到低的順序遞減排序。用Python實現具體代碼如下：

運行結果如圖4.15所示。