冒泡排序算法

2024年第12期的《算法世界》欄目介紹了選擇排序算法，它和下面要介紹的冒泡排序算法原理類似，都是和排序有關的算法。排序是計算機處理工作時經常做的一項工作，據統計，計算機約有25%的工作時間花在排序上。排序如此重要，所以人們發明了各種排序的算法。

冒泡排序是最出名、最常用的排序算法之一，它名字形象且操作簡單，其流程是這樣：假設有一組需要排序的數據，將數據中的第1個數字與第2個數字比大小，如果第2個數字大于第1個數字，則將兩者交換位置，否則不變；接著，將第2個數字與第3個數字比大小，如果第3個數字比第2個數字大，將兩者交換位置，否則不變……就這樣一直比到最后兩個數字，這個過程就被稱為“第1趟排序”，經過這一趟比較和交換，最大的數據就被排到序列的最后；接著，對剩余的數據繼續進行第2趟、第3趟排序，直到全部數據都按由小到大排列。

例：游泳時間排序

安奇奇最近在練習游泳，小酷龍記錄了安奇奇最近5次的練習時間：“58分鐘，43分鐘，61分鐘，39分鐘，52分鐘?！彼麤Q定用冒泡排序算法對這5個數據按從小到大的順序排序，為后續針對性的練習提供參考。

請問小酷龍完成第2趟排序后，新的數據排列是怎樣的？（ ）

A、43，39，61，58，52 B、39，43，52，58，61

C、39，58，43，52，61 D、43，39，52，58，61

答案：D

解析：我們可以將冒泡排序算法的完整過程列出來，順序如下。

初始狀態

58 43 61 39 52

第1趟排序

①從頭開始比較第1個數和第2個數：58和43，58更大，兩個數據交換位置。

43 58 61 39 52

②繼續比較第2個數和第3個數：58和61，61更大，位置不變。

③再比較第3個數和第4個數：61和39，61更大，兩個數據交換位置。

43 58 39 61 52

④最后比較末尾兩個數：61和52，61更大，兩個數據交換位置。

第1趟排序完成，新的數據列表變成：

43 58 39 52 61

最大的數字61就像最重的氣泡，最先“沉”到底。

第2趟排序

61不參與排序。

①從頭開始，比較第1個數和第2個數：43和58，58更大，位置不變。

②繼續比較第2個數和第3個數：58和39，58更大，兩個數據交換位置。

43 39 58 52 61

③最后比較第3個數和第4個數：58和52，58更大，兩個數據交換位置。

第2趟排序完成，新的數據列表變成：

43 39 52 58 61

第2 大的數字58歸位。

第3趟排序

58和61不參與排序。

①再次從頭開始，比較第1個數和第2個數：43和39，43更大，兩個數據交換位置。

39 43 52 58 61

②最后比較第2個數和第3個數：43和52，52更大，位置不變。

③沒有數據再需要交換位置，排序完成。

計算思維訓練

同學們應該已經發現了，在整個排序過程中，較小的數不斷往前移，就像氣泡不斷向上冒一樣，冒泡排序算法因此得名。不過，冒泡排序算法雖然簡單，但它也是“名聲最壞”的排序算法之一，因為它需要的步驟實在太多了。

練一練：

安奇奇和幾個小伙伴想知道誰唱歌更好聽，分別唱了同一首歌，唱歌軟件給出了“68分，55分，72分，46分，60分”的成績。安奇奇打算用冒泡排序算法整理數據。

當成績排序為“55，46，60，68，72”時，經歷了幾趟排序過程？（ ）

A.1 B.2 C.3 D.4