排序演算法筆記 1 – Bubble Sort (泡沫排序法)

先來介紹最經典的 bubble sort，雖然是最經典的不過其實也有很多種寫法，接著就來一個一個慢慢解釋。

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(n²)
平均：O(n²)

6. 參考資料

大話資料結構(全新彩色版)
一起用 JavaScript 來複習經典排序法吧！
JavaScript 學演算法（八）- 排序演算法
The Coding Interview Bootcamp: Algorithms + Data Structures
資料結構與演算法 (JavaScript)

看完這篇文章是不是想換工作了呢（咦？那就千萬別錯過 2024 職涯博覽會！想換工作的，有機會在博覽會遇見更好的另一半，不想換工作的，有機會在博覽會遇見更好的工作！趕快點擊下面的 banner，拯救你的人生！！！https://s.yourator.co/jimmy

如果覺得我的文章有幫助的話，歡迎幫我的粉專按讚哦~謝謝你！