[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; // 最后回传排序好的阵列
}