氣泡排序法(Bubble Sort)是最容易理解和實作的排序演算法，但其時間複雜度在排序法當中算是最差的一個。主要觀念是從頭開始逐一比較相鄰兩筆資料，將較大值往後移動位置，直到最後，資料就會從最小值依序排到最大值。

此網頁有小動畫可以參考看看，非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Bubble/1.php

接著我們來實作吧!完成後會討論其時間複雜度~

最一開始我們建立一個bubbleSort()函式，接著在裡面寫兩個 for 迴圈，外層 for 是負責整個資料列的元素遍歷，確保所有資料都有做過排序，不過最後一個資料不需要作排序，因為當其他的資料都作好排序時，最後一個資料已經變成是排序順序中的最大或最小值了，因此 i 在 length - 1 的範圍作迴圈。

內層 for 則是將未排序的資料進行排序，因此 j 的範圍必須扣掉 已排序完成的資料數 (i) 並且減1

接著完成內層 for 的內容:
將兩個數作比較，前者較大就作交換，此時就完成bubble sort 了!

function bubbleSort(data) {
  const length = data.length;
  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      let temp;
      // 前者較大就作交換
      if (data[j] > data[j + 1]) {
        temp = data[j + 1];
        data[j + 1] = data[j];
        data[j] = temp;
      }
      console.log(data);
    }
  }
}

bubbleSort([1, 234, -5, 78, -182, 45]);

透過內層 for 內的console.log(data);可以看到排序過程:

氣泡排序法優化(2021/06/29 更新)

如果一個陣列提早排序好的話，我們可以使用一個 flag 去判斷是否還有在做交換陣列的值，沒有的話就跳出迴圈結束比對。

function bubbleSort(data) {
  const length = data.length;
  let noSwaps;
  for (let i = 0; i < length - 1; i++) {
    noSwaps = true;
    for (let j = 0; j < length - 1 - i; j++) {
      let temp;
      // 前者較大就作交換
      if (data[j] > data[j + 1]) {
        temp = data[j + 1];
        data[j + 1] = data[j];
        data[j] = temp;
        noSwaps = false;
      }
      console.log(data);
    }
    if(noSwaps) break;
  }
}

bubbleSort([1, 2, 5, 3, 4, 6]);

時間複雜度:

• 最佳時間複雜度：Ο(n)
  當資料已經預先排序好的狀況
• 平均時間複雜度：O(n^2)
  當目標資料排序正好和原本資料排序狀況相反，例如由大到小變成
• 最差時間複雜度：O(n2)
  第n筆資料，平均比較(n-1)/2次

這次的完整程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day17-bubble-sort.js

明天將會介紹選擇排序 Selection Sort!