【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])