先來介紹最經典的 bubble sort，雖然是最經典的不過其實也有很多種寫法，接著就來一個一個慢慢解釋。
Table of Contents
1. Bubble Sort 方法一
1.1 原理解釋
這個方法是最經典的方法，倆倆比較，如果左邊比右邊大就交換 (將大的浮到右邊)：
假設有一陣列：[9, 6, 7, 3]
第一輪(i = 0)比較：
首先比較前兩個，若順序錯誤則對調，正確則不做任何動作：
接著往下比較第二和第三個：
比較第三和第四個：
第一輪比較完後可以發現，最大的元素透過這一輪比較，浮到最右邊了，在第 i 輪比較完後，會有 i + 1 個元素排列好，因此 j 需要跑的回圈數量為：n – (i + 1)，n 為陣列長度。
接著第二輪 (i = 1) 比較 (排列好的元素用白底表示)：
第三輪 (i = 2) 比較：
最後排列好的元素：
1.2 JavaScript 實作
function bubbleSort1(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < (n - i - 1); j++) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 以上 3 行可以縮寫成 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
}
}
}
return arr;
}2. Bubble Sort 方法二
2.1 原理解釋
這個方法和上一個方法不同的是比較的元素從相鄰變成跳著比較：
第一輪 (i = 0) 比較，將陣列中的第 0 個元素和其他所有元素比較，順序錯誤則對調：
這個方法和上個方法不同的是排列好的順序會從陣列的頭開始。
接著第二輪 (i = 1) 比較：
由此可以發現：跑到第 i 輪的時候，陣列前 i 個元素就是排好的狀態。
第三輪比較：
排列好的陣列：
2.2 JavaScript 實作
function bubbleSort2(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}3. Bubble Sort 方法三
3.1 原理解釋
這個方法算是第一種方法的另外一個寫法，原理是一樣，只是讓最小的元素先沉下去：
第一輪 (i = 0) 排序：
第二輪 (i = 1) 排序：
第三輪 (i = 2) 排序：
3.2 JavaScript 實作
function bubbleSort3(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = n - 1; j > i - 1; j--) {
if (arr[j] > arr[j + 1]) {
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}4. Bubble Sort 方法四：優化版
宣告一個 swapped 變數，在跑第二輪 i 迴圈時根據 swapped 變數來判斷上一輪是否有 swap 的動作，如果沒有代表此陣列已經排序好了，就不需要再跑第二輪以後的 i 迴圈：
4.1 JavaScript 實作
function bubbleSortOpt(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false
for (let j = 0; j < (n - i - 1); j++) {
if (arr[j] > arr[j + 1]) {
swapped = true;
const temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (swapped === false) {
break;
}
}
return arr;
}5. Time Complexity
最佳：O(n)
最差：O(n2)
平均：O(n2)
6. 參考資料
大話資料結構(全新彩色版)
一起用 JavaScript 來複習經典排序法吧！
JavaScript 學演算法（八）- 排序演算法
The Coding Interview Bootcamp: Algorithms + Data Structures
資料結構與演算法 (JavaScript)
如果覺得我的文章有幫助的話，歡迎幫我的粉專按讚哦~謝謝你！