Skip to content

选择排序

· 2 min

基本概念#

选择排序，英语为 Selection Sort，这是一种简单直观的排序算法，其核心思想在于每次从待排序的数组中选出最小（或最大）的元素，并将其放到数组的起始（或末尾）位置，从而逐步构建有序区间。

它的工作原理是：

  1. 划分区间：将数组分为两部分：已排序区间 和 未排序区间。初始时已排序区间为空，未排序区间即整个数组。
  2. 选择最小元素：在未排序区间中，找到最小（或最大）的元素。
  3. 交换位置：将找到的最小元素与未排序区间的第一个元素交换位置，这样该元素就加入到了已排序区间中。
  4. 重复操作：对剩余的未排序区间重复上述步骤，直到整个数组排序完毕。

selectsort

代码实现#

function selectionSort(arr) {
  const n = arr.length


  // 指向未排序区间的起始位置
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i // 假设当前的 i 所对应的数就是最小值
    // 内层for循环每次都是从 i 的右侧那一个到最后一个
    // 内层for循环的目的是找到最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      // 做一个交换
      let temp = arr[i]
      arr[i] = arr[minIndex]
      arr[minIndex] = temp
    }
  }
}


const arr = [5, 3, 8, 4, 2]
selectionSort(arr)
console.log(arr)

复杂度#

稳定性#

选择排序在每一轮选择中会改变元素的相对顺序，因此选择排序是一种 不稳定 的排序。

-EOF-