选择 | Autumn 博客

function selectSort(arr) {
  // 外循环：未排序区间为 [i, arr.length-1]
  for (let i = 0; i < arr.length - 1; 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]]
  }
}

let arr = [64, 34, 25, 12, 22, 11, 90]
console.log('排序前的数组: ', arr)
let sortedArr = selectSort(arr)
console.log('排序后的数组: ', sortedArr)

选择排序空间复杂度为 O(1)，是一种原地排序算法.

选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2).

选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

比如 [5，8，5，2，9] 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。