选择排序

场景引入

想象你面前有一排高矮不同的人，要按身高从矮到高排列。最直觉的做法是什么？从这一排人中找到最矮的，放到第一位；然后从剩下的人中再找最矮的，放到第二位……这就是选择排序的核心思路。

选择排序的逻辑极其简单，代码量少，非常适合作为学习排序算法的第二站。虽然它在实际工程中很少使用（始终 O(n²)），但理解它有助于对比其他排序算法的优势。

核心思路

选择排序的核心操作是：在未排序部分中找到最小元素，将其与未排序部分的第一个元素交换。

算法步骤

将数组分为已排序区间（左侧）和未排序区间（右侧），初始时已排序区间为空
遍历未排序区间，找到最小元素的下标 minIdx
将 minIdx 处的元素与未排序区间的第一个元素交换
已排序区间向右扩展一位
重复步骤 2-4，直到未排序区间只剩一个元素

与冒泡排序的区别

冒泡排序每轮通过相邻交换把最大值"冒泡"到末尾，交换次数可能很多。选择排序每轮只做一次交换（找到最小值后直接放到正确位置），因此交换次数最多 n-1 次，远少于冒泡排序。

算法流程图

可视化演示

加载可视化中...

代码实现

javascript

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i; // 假设未排序部分第一个元素最小
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j; // 更新最小值下标
      }
    }
    // 将最小值交换到已排序区间的末尾
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

关键点

外层循环 i 表示已排序区间的右边界
内层循环在 [i+1, n) 中寻找最小值
if (minIdx !== i) 避免不必要的自交换

复杂度分析

	时间复杂度	空间复杂度
最好	O(n²) — 即使已有序，仍需遍历找最小值	O(1)
平均	O(n²)	O(1)
最坏	O(n²)	O(1)

稳定性：不稳定。交换操作可能改变相同元素的相对顺序。例如 [5a, 5b, 2]，第一轮将 5a 和 2 交换后变成 [2, 5b, 5a]，两个 5 的顺序改变了。

比较次数：无论数据如何分布，比较次数恒为 n(n-1)/2。

交换次数：最多 n-1 次，最少 0 次（已有序时）。这是选择排序相对于冒泡排序的优势——当数据交换成本高时，选择排序更优。

面试要点

选择排序是不稳定排序，这是常见面试考点
时间复杂度始终 O(n²)，无法通过任何优化改善（不像冒泡排序可以提前终止）
交换次数少是它唯一的优势场景

LeetCode 练习

LC 912. 排序数组 — 可用选择排序实现，但大数据量会超时
LC 75. 颜色分类 — 选择排序思想的变种，值域有限时的优化

选择排序 ​

场景引入 ​

核心思路 ​

算法步骤 ​

与冒泡排序的区别 ​

算法流程图 ​

可视化演示 ​

代码实现 ​

关键点 ​

复杂度分析 ​

面试要点 ​

LeetCode 练习 ​