[Easy] 選擇排序法 Selection Sort

選擇排序法(Selection Sort)，是程式面試中很常出現的入門考題。以下我們要介紹選擇排序法(Selection Sort) 的作法和程式碼。

如果我們有個 [8, 5, 7, 6] 陣列，我們要把他排成 [5, 6, 7, 8]，用選擇排序法(Selection Sort) 可以這麼做：

• 用迴圈迭代過未排序區域
• 找到未排序區域中最小的值
• 選擇該最小值，放到未排序區的最左邊，並標記成已排序
• 重複上述步驟直到排序完成

以[8, 5, 7, 6] 陣列具體來說，會是這樣的過程：

• 掃過未排序 [8, 5, 7, 6] 陣列，最小值為 5，把 5 換到未排序的最左邊，並標記成已排序
• 掃過未排序的 [8, 7, 6] 陣列，最小值為 6，把 6 換到未排序的最左邊，並標記成已排序
• 掃過未排序的 [7, 8] 陣列，最小值為 7，7 已經是未排序的最左邊，所以跟自己換，並標記成已排序
• 未排序陣列只剩下 [8] 所以跟自己換，並標記已排序
• 這樣就大功告成了！

選擇排序法(Selection Sort) 程式碼

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 初始化最小值的索引
    let minIndex = i;
    // 從未排序區中找最小值
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 在過程中，只要值比較小，就更新索引
      }
    }
    // 把找到的最小值，與還未排序區域的最左邊元素交換位置
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr; // 最後回傳排序好的陣列
}