气泡排序法是，从第一个元素开始，和相邻数字比大小，若有需要就交换位置。因此也可称为交换排序法。它的时间复杂度是 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)