iT邦幫忙

2021 iThome 鐵人賽

DAY 8
0
自我挑戰組

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

【Day 08】Sorting:Selection Sort 選擇排序法 ( 用 JavaScript 學演算法 )

選擇排序法的概念是,將陣列分為兩個部分,每次掃描未排序的部分時,從數列中拿出最小的數,丟到另一邊,最後就會得到一個完成排序的陣列。它的時間複雜度是 O(n^2)。

一、步驟觀察

  • 將陣列視為已排序(標記)、未排序兩個部分
  • 遍歷未排序的陣列
    • 從未排序的陣列中,取出最小值
    • 與第一個值替換位置
    • 向右移動標記

二、實際操作

使用哪種資料結構:Array

  • 遍歷陣列
    • 將第一個元素設定為最小值
    • 遍歷未排序的元素
      • 如果未排序元素 < 當前最小值
        • 將未排序元素設定為當前最小值
    • 將最小值和第一個未排序的元素交換位置

邏輯:

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

  for i (0 to len-1) do
    let minIndex = i

    for j (i+1 to len-1) do
      if (arr[j] < arr[minIndex]) then
        minIndex = j
      end if
    end for
    swap(arr, i, minIndex)
  end for

  func swap(arr, firstIndex, minIndex):
    temp = arr[firstIndex]
    arr[firstIndex] = arr[minIndex]
    arr[minIndex] = temp
  end func

程式碼實作:

debugger

function swap(arr, firstIndex, minIndex) {
  temp = arr[firstIndex]
  arr[firstIndex] = arr[minIndex]
  arr[minIndex] = temp
}

function selectionSort(arr) {

  for (let i = 0; i < arr.length; i++) {
    let minIndex = i

    for (j=i+1 ; j<arr.length ; j++) {
      minIndex = (arr[j]<arr[minIndex]) ? j : minIndex
    }

    swap(arr, i, minIndex)
    console.log(arr)
  }
}

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

三、時間複雜度 Big O

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

上一篇
【Day 07】Sorting:Insertion Sort 插入排序法 ( 用 JavaScript 學演算法 )
下一篇
【Day 09】Sorting:Bubble Sort 氣泡排序法 ( 用 JavaScript 學演算法 )
系列文
【用 JS 學演算法】前端工程師學徒9

尚未有邦友留言

立即登入留言