冒泡排序是幾種經典並且形象的排序方法之一，在我大一時候老師講的第一個排序演算法，記得當時還放了段日本小視頻，幾個人每個人代表一個數字，互相交換位置表示排序過程，不過我當時完全沒懂。後來為了應付考試只是背下來兩重循環、交換順序，但是每個循環代表什麼，交換過程都不是很清楚。這種排序方法在考試和面試里還是有一些用處的，值得花一點時間搞清楚。下面我來用比較簡單、清晰的文字講一下。

既然這種排序就叫冒泡排序，首先要說的就是『冒泡』。有一種解釋是將一個數字當做泡泡進行冒泡，但是我感覺用一個泡泡包住兩個數字進行交換操作更容易理解。比如說我們要從小到大排序下面一組數字：

[3, 6, 12, 7, 5, 1, 13, 8, 10, 2, 4, 9, 11]

現在有一個泡泡，它從左向右冒出去(也可以把頭轉向右邊，想像成泡泡就是從下向上)，這個泡泡最多容下兩個數字

在它向右冒的過程，會將泡泡內的兩個數字比較，將較大的數字『交換』至右側

當這個泡泡冒至最右，就完成了一次冒泡，這組數字會變為：

[3, 6, 7, 5, 1, 12, 8, 10, 2, 4, 9, 11, 13]

加粗的兩個數字是這次冒泡移動的數字，並且這組數字最大『13』的一個被移動到了最後，

這就是演算法最核心的一部分：冒泡一次就將最大的數字移動到最後面

把這一次冒泡的『過程』寫成代碼就是：

let arr = [3, 6, 12, 7, 5, 1, 13, 8, 10, 2, 4, 9, 11]
for ( let i=0; i<(arr.length-1); i++ ) { // 泡泡需要比較(數組長度減一)次
 let bubble = arr[i] // 泡泡內的兩個數字是arr[i]和arr[i+1]
 if ( arr[i] > arr[i+1] ) { // 如果左邊數字大於右邊數字，則交換
 arr[i] = arr[i+1] // if內是交換數字,也可以用你喜歡的方式:
 arr[i+1] = bubble // 比如[arr[i], arr[i+1]] = [arr[i+1], arr[i]]
 }
}
// 進行一次交換後，arr就會變為 [3, 6, 7, 5, 1, 12, 8, 10, 2, 4, 9, 11, 13]

這一部分也就是常見的冒泡排序演算法中的內循環。

當我們把這組數字的每一個數字都進行這樣的冒泡過程，那這組數字就會排序完成，這一過程就是常見演算法的外循環。實際上在倒數第二個數字冒泡過後，排序已經完成，因為最小的數字會被擠到最初的位置。

let arr = [3, 6, 12, 7, 5, 1, 13, 8, 10, 2, 4, 9, 11]
for (let j=0; j<(arr.length-1); j++) { // 這一層循環只是重複進行冒泡過程
 for ( let i=0; i<(arr.length-1); i++ ) {
let bubble = arr[i]
if ( arr[i] > arr[i+1] ) {
arr[i] = arr[i+1]
arr[i+1] = bubble
}
}
}

但是如果一組數字只有一個數字是亂序，比如[1, 2, 3, 4, 9, 5, 6, 7, 8]

只要冒泡一次就會變成正常順序，這是我們可以設定一個開關：bubbleSwitch

當泡泡內部進行交換時，將開關打開，說明此時還是亂序狀態；在進行每輪冒泡之前將開關重置為關閉，之後在進行冒泡過程，如果冒泡結束時開關是關閉狀態，則說明這時已經是排好序的狀態就不用將每個數字都進行冒泡。

這一段過程可以用while來替代外側for循環更容易理解：

let arr = [3, 6, 12, 7, 5, 1, 13, 8, 10, 2, 4, 9, 11]
let bubbleSwitch = true
while ( bubbleSwitch == true ) {
bubbleSwitch = false
for ( let i=0; i<(arr.length-1); i++ ) {
let bubble = arr[i]
if ( arr[i] > arr[i+1] ) {
arr[i] = arr[i+1]
arr[i+1] = bubble
bubbleSwitch = true
}
}
}

還有一些其他的優化方式，就不在這裡多介紹了。這篇文章就是簡單介紹一下冒泡排序的過程，希望能對大家有所幫助。


推薦閱讀：
相关文章