選擇排序法（Selection sort）

最直覺的排序法。

概念

每次都從數列中找出最小的，然後移到最左邊。

流程圖：

步驟

repeeat (numOfElement - 1) time 
  set the first unsorted element as the minimum
  for each of the unsorted elements
  if element < currentMinimum
    set element as new minumum
  swap minimum with first unsorted position

遍歷所有數字（迴圈）
  把第一個數字當作最小值
  遍歷後面的未排序數字（迴圈）
    如果數字 < 目前的最小值
      更新最小值成這個數字
  迴圈結束
  把第一個數字跟最小值交換位置
迴圈結束

實作

function selectionSort(arr) {
  // 遍歷所有數字
  for(let i=0; i<arr.length; i++) {
    // 把第一個數字當作最小值
    let minumum = arr[i]
    /*
      儲存最小值的位置：
      注意如果寫成 null 會有問題，
      因為有可能第一個數字就是最小值，
      indexOfMinumum 就會不會被更新，保留 null 值
      這樣會導致最後交換時出錯（unSotredNumbers[null]）

      所以正確的作法是把最小值設為第一個數的位置，
      當第一個數就是最小值時，也只是把自己跟自己交換位置而已
    */
    let indexOfMinumum = i
    // 遍歷後面未排序的數字
    for (let j=i+1; j<arr.length; j++) {
      // 如果數字 < 目前最小值
      if (arr[j] < minumum) {
        // 更新最小值
        minumum = arr[j]
        // 更新最小值位置
        indexOfMinumum = j
      }
    }
    /*
      交換位置：
      1. 儲存第一個數字
      2. 把第一個數設成最小值
      3. 把最小值設成第一個數字
    */
    let temp = arr[i]
    arr[i] = minumum
    arr[indexOfMinumum] = temp
  }
  // 排序好的數字
  return arr
}
const unSotredNumbers = [3, 4, 28, 47, 16, 15, 40 ,5, 7, 12, 40, 8, 39, 50, 32, 87]
console.log(selectionSort(unSotredNumbers))
// [3, 4, 5, 7, 8, 12, 15, 16, 28, 32, 39, 40, 40, 47, 50, 87]

關於 null 的 bug 可以參考這裡：

[1 ,2 ,3] length:3

初始化設定
i=0
minumum: 1
indexOfMinumum: null

找出最小值
j=1
Not found 

交換數字
let temp = unSotredNumbers[i] =>  1
unSotredNumbers[i] = minumum => 1 = 1
unSotredNumbers[null] = temp => unSotredNumbers.null = 1


初始化設定
i=1
minumum: 2
indexOfMinumum: null

找出最小值
j=2
Not found 

交換數字
let temp = unSotredNumbers[i] =>  2
unSotredNumbers[i] = minumum => 2 = 2
unSotredNumbers[null] = temp => unSotredNumbers.null = 2


初始化設定
i=2
minumum: 3
indexOfMinumum: null

找出最小值
j=3
Not found 

交換數字
let temp = unSotredNumbers[i] =>  3
unSotredNumbers[i] = minumum => 3 = 3
unSotredNumbers[null] = temp => unSotredNumbers.null = 3

最後結果
[1, 2 ,3, null: 3]