iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

【用 JS 學演算法】前端工程師學徒系列 第 9

【Day 09】Sorting:Bubble Sort 氣泡排序法 ( 用 JavaScript 學演算法 )

氣泡排序法是,從第一個元素開始,和相鄰數字比大小,若有需要就交換位置。因此也可稱為交換排序法。它的時間複雜度是 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)

上一篇
【Day 08】Sorting:Selection Sort 選擇排序法 ( 用 JavaScript 學演算法 )
系列文
【用 JS 學演算法】前端工程師學徒9

尚未有邦友留言

立即登入留言