氣泡排序法是，從第一個元素開始，和相鄰數字比大小，若有需要就交換位置。因此也可稱為交換排序法。它的時間複雜度是 O(n^2)。

一、步驟觀察

• 遍歷未排序元素，作以下動作
  • 與相鄰元素做比較
    • 如果左邊大於右邊元素
      • 交換位置
• 從後面向左移動標記

( 圖片來源 wiki )

二、實際操作

使用哪種資料結構：Array

• 設定 for loop 作為移動標記用 (右側開始)
• 遍歷未排序的元素
  • 如果左邊元素 > 右邊元素
    • 交換位置
• 向左移動標記

邏輯：

  arr <- an unsorted array of integers
  let len be the length of arr

  for i (len-1 to 1) do
    for j (0 to i-1) do
      if (arr[j]>arr[j+1]) then
        swap(arr, j, j+1)
      end if
    end for
  end for

  func swap(arr, leftIndex, rightIndex):
    temp = arr[leftIndex]
    arr[leftIndex] = arr[rightIndex]
    arr[rightIndex] = temp
  end func

程式碼實作：

debugger

function swap(arr, leftIndex, rightIndex) {
  temp = arr[leftIndex]
  arr[leftIndex] = arr[rightIndex]
  arr[rightIndex] = temp
}

function bubbleSort(arr) {

  for (let i = arr.length-1; i >= 1; i--) { // 已排序元素的控制器

    console.log(i)
    for (let j = 0; j <= i-1; j++) {
      if (arr[j] > arr[j+1]) {
        swap(arr, j, j+1)
      }
      console.log(arr)
    }

  }
}

bubbleSort([8, 9, 2, 5, 1])

三、時間複雜度 Big O

• 總共比較了 1+2+3+...+(n-1)
• 也就是 n*(n-1)/2
• 時間複雜度會忽略係數，所以為 O(n^2)