bubble sort

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

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

1. Bubble Sort 方法一

1.1 原理解釋

這個方法是最經典的方法,倆倆比較,如果左邊比右邊大就交換 (將大的浮到右邊):

假設有一陣列:[9, 6, 7, 3]

bubble sort

第一輪(i = 0)比較:

首先比較前兩個,若順序錯誤則對調,正確則不做任何動作:

bubble sort

接著往下比較第二和第三個:

bubble sort

比較第三和第四個:

bubble sort

第一輪比較完後可以發現,最大的元素透過這一輪比較,浮到最右邊了,在第 i 輪比較完後,會有 i + 1 個元素排列好,因此 j 需要跑的回圈數量為:n – (i + 1),n 為陣列長度。

接著第二輪 (i = 1) 比較 (排列好的元素用白底表示):

bubble sort
bubble sort

第三輪 (i = 2) 比較:

bubble sort

最後排列好的元素:

bubble sort

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 原理解釋

這個方法和上一個方法不同的是比較的元素從相鄰變成跳著比較:

bubble sort

第一輪 (i = 0) 比較,將陣列中的第 0 個元素和其他所有元素比較,順序錯誤則對調:

bubble sort
bubble sort
bubble sort

這個方法和上個方法不同的是排列好的順序會從陣列的頭開始。

接著第二輪 (i = 1) 比較:

bubble sort
bubble sort

由此可以發現:跑到第 i 輪的時候,陣列前 i 個元素就是排好的狀態。

第三輪比較:

bubble sort

排列好的陣列:

bubble sort

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) 排序:

bubble sort
bubble sort
bubble sort

第二輪 (i = 1) 排序:

bubble sort
bubble sort

第三輪 (i = 2) 排序:

bubble sort

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)

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

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

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top