三分钟带你了解选择排序

什么是选择排序？

选择排序是一种常见的排序算法，其基本思想是：首先从未排序的数组中选取最小的元素，然后放到已排序的数组的末尾。重复此步骤，直到所有的元素都排序完成。因为每次都选取最小的元素，所以称之为选择排序。

/**
 * 选择排序
 * @param {array} arr - 待排序的数组
 */
function selectionSort(arr) {
  const len = arr.length
  let minIndex // 存放当前未排序中最小元素的下标
  for(let i = 0; i < len -1; i++) {
    // 遍历未排序区间的所有元素，找到最小元素的下标
    minIndex = i
    for(let j = i + 1; j < len; j++) {
      if(arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    // 将最小元素和当前遍历的第一个元素交换位置
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
}

选择排序的时间复杂度和稳定性如何？

选择排序的时间复杂度为O(n ^ 2)，因为每次寻找最小值需要遍历未排序的区间，而遍历的长度逐渐减小，所以最终的时间复杂度为 (n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2 = O(n ^ 2)。其空间复杂度为O(1)，因为交换时只需要使用一个临时变量。但是选择排序是一种不稳定的排序算法，因为交换可能会改变相同元素的相对位置。

选择排序的优化

可以发现，在每次寻找未排序区间的最小元素时，都需要遍历整个区间，造成了很多不必要的工作。为了减少这些工作量，可以记录一下最小值的下标，遍历完区间之后再进行交换。同时，如果当前遍历的元素已经是最小值，就不用再进行交换了，这也可以提升算法的效率。

/**
 * 优化后的选择排序
 * @param {array} arr - 待排序的数组
 */
function selectionSort2(arr) {
  const len = arr.length
  let minIndex // 存放当前未排序中最小元素的下标
  for(let i = 0; i < len -1; i++) {
    // 遍历未排序区间的所有元素，找到最小元素的下标
    minIndex = i
    for(let j = i + 1; j < len; j++) {
      if(arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    // 如果最小值不是当前遍历的元素，则交换位置
    if(minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
}

选择排序和其他排序算法的比较

相比于冒泡排序，选择排序的交换次数更少，所以速度更快。但是对于大规模无序的数组，还是插入排序和快速排序更快，因为选择排序的时间复杂度始终是O(n ^ 2)。同时，选择排序比较适合数据量比较小的情况，因为在数据量不大的情况下，时间复杂度不会带来太大的负担。

/**
 * 插入排序
 * @param {array} arr - 待排序的数组
 */
function insertionSort(arr) {
  const len = arr.length
  let preIndex, current
  for(let i = 1; i < len; i++) {
    preIndex = i - 1
    current = arr[i]
    while(preIndex >=0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
}