iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
自我挑戰組

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

【Day 07】Sorting:Insertion Sort 插入排序法 ( 用 JavaScript 學演算法 )

插入排序法是將陣列中未排序的元素,逐一與排序好的資料作比較。它的時間複雜度是 (O(n^2))。

一、步驟觀察

  • 標記第一個元素作為已排序的部分
  • 遍歷未排序的部分,作以下動作
    • 取第一個未排序的元素
    • 與已排序的元素作比較
      • 移動出正確位置,然後插入未排序的元素
    • 向右移動標記

二、實際操作

使用哪種資料結構:Array

  • 將第一個元素標記為已排序
  • 遍歷未排序的元素
    • 取第一個未排序元素
    • 遍歷已排序的元素 (從後到前)
      • 如果已排序元素 > 未排序元素
        • 已排序元素向右移
      • 否則插入未排序的元素 (原位置或空格)

邏輯:

  arr <- an unsorted array of integers
  let len be the length of arr
  
  for i (1 t0 len-1) do
    key = arr[i]
    j = i-1
    while j>=0 && key<arr[j]
      arr[j+1] = arr[j]
      j--
    end while
    arr[j+1] = key
  end for

程式碼實作:

debugger
function insertionSort(arr) {

  for (let i = 1; i < arr.length; i++) {
    let key = arr[i] // 第一個未排序的元素
    let j = i-1 // 已排序元素的控制器
    console.log(key)

    while (j>=0 && key<arr[j]) { // 移動出正確位置
      arr[j+1] = arr[j]
      console.log(arr)
      j--
    }
    arr[j+1] = key // 插入未排序元素
    console.log(arr)
  }
}

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

三、時間複雜度 Big O

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

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

尚未有邦友留言

立即登入留言