[排序演算法]Bubble Sort — 氣泡排序法

bubble sort 的概念就是像泡泡一樣 ，越大的數字會漸漸的往右邊浮

比較相鄰的元素 ，兩兩比大小， 如果前面的數字大於後面的數字就交換順序，一路把最大值往後塞。

• 跑完第 1 回合，該陣列的最後一個數字就會是最大的
• 跑完第 2 回合，該陣列的倒數第 2 個數字就會是第 2 大的
• 規律為執行完第 n 回合，第 n 大的數字就會出現在倒數第 n 個位置

函式內部實作為:

假設現在有一個陣列[29, 10, 14, 37, 14]要用氣泡排序法來排序的話

1. 29 與 10 相比 29 較大，所以 29 與 10 交換，此時 arr = [10, 29, 14, 37, 14]

2. 29 與 14 相比 29 較大，所以 29 與 14 交換， 此時 arr = [10, 14, 29, 37, 14]

3. 29 與 37 相比 29 較小，所以 29 不跟 37 交換， 此時 arr = [10, 14, 29, 37, 14]

4. 37 與 14 相比 37 較大，所以 37 與 14 交換， 此時 arr = [10, 14, 29,14, 37]

此時第一回合結束，可以發現最大的數字已經移動到最後面，依序執行 n-1 回合之後，就可以將全部的數字由小排到大了。

為甚麼是 n-1 回合? 假如今天有個陣列長度為 5，當 index1 ~index4 都是排序好的，那麼 index0 自然也會是最小的，就不需要再跑一次回合，所以只要跑 (n-1)，5–1=4 回合即可。

連續的步驟會如下圖所示

用 js 實作氣泡排序法

const bubble = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
};

第一個迴圈的長度為 arr.length-1，因為經過一輪的排列，直到最後一回合，剩下的那個值必定為最小值，就不需要比較，可以扣掉一次，那第二個迴圈的長度為甚麼是 arr.length-i-1 ?因為經過 i 回合後，倒數第 i 個數字都是經過排序的，那麼在跑迴圈的時候就可以排除掉，不需要檢查了。

時間複雜度

👍 在最差的情況下，時間複雜度是 O(n²)

👎 在最佳的情況下，時間複雜度是 O(n)

🤚 在平均情況下，時間複雜度為 O(n²)