首页/数据结构/07-sorting/选择排序 🔗 在 Obsidian 中打开
数据结构 · 07-sorting

选择排序

重要度 ★★ 数据结构/排序排序选择排序408考研
速查
选择排序每趟从待排序部分选最小（或最大）元素，与待排序部分首个元素交换；共 $n-1$ 趟。比较次数始终 $\frac{n(n-1)}{2}$（与初始序列无关），交换最多 $n-1$ 次，空间 $O(1)$，不稳定。

核心概念 ▾

选择排序（Selection Sort）是一种简单直观的排序算法，核心思想是：每一趟从待排序序列中选取关键字最小（或最大）的元素，放入已排序序列的末尾。

  • 已排序序列：序列前部分，已经有序
  • 未排序序列：序列后部分，尚未处理
关键特性
  1. 比较次数始终为 $\frac{n(n-1)}{2}$，与初始序列状态无关（区别于其他排序）
  2. 每一趟只进行一次交换
  3. 与交换排序（不断交换）不同，与插入排序（移动元素）也不同

算法步骤 ▾

  1. 初始已排序序列为空，所有元素在未排序序列中
  2. 在未排序序列中找到关键字最小的元素
  3. 将该最小元素与未排序序列的第一个元素交换
  4. 已排序序列增加一个元素，未排序序列减少一个
  5. 重复 2–4，共执行 $n-1$ 趟

代码实现 ▾

void SelectSort(int A[], int n) {
    int i, j, min;
    for (i = 0; i < n - 1; i++) {   // 共 n-1 趟
        min = i;                    // 记录最小元素下标
        for (j = i + 1; j < n; j++) // 在未排序中找最小
            if (A[j] < A[min]) min = j;
        if (min != i) {             // 交换
            int temp = A[i]; A[i] = A[min]; A[min] = temp;
        }
    }
}

手算示例 ▾

对序列 {49, 38, 65, 97, 76, 13, 27, 49*} 进行选择排序：

趟次选中最小（位置）交换后序列
113（5）[13] 38 65 97 76 49 27 49*
227（6）[13 27] 65 97 76 49 38 49*
338（6）[13 27 38] 97 76 49 65 49*
449（5）[13 27 38 49] 76 97 65 49*
549*（7）[13 27 38 49 49*] 97 65 76
665（6）[13 27 38 49 49* 65] 97 76
776（7）[13 27 38 49 49* 65 76 97]
注意本例结果中 49 仍在 49* 前（恰好保持顺序），但这不代表稳定——见稳定性分析的反例。

时间 / 空间复杂度与稳定性 ▾

情况时间复杂度说明
最好$O(n^2)$序列有序
平均$O(n^2)$随机输入
最坏$O(n^2)$序列逆序
空间$O(1)$原地排序
  • 比较次数：始终 $\sum_{i=0}^{n-2}(n-1-i) = \frac{n(n-1)}{2} \to O(n^2)$
  • 交换次数：最多 $n-1$ 次
稳定性选择排序是不稳定的。反例 {5, 8, 5*, 2}：第 1 趟选最小 2 与位置 0 交换 → {2, 8, 5*, 5}，5 与 5* 相对顺序改变。

易错点 ▾

注意
  1. 选择排序不稳定，不要误以为稳定
  2. 比较次数始终 $\frac{n(n-1)}{2}$，与初始序列无关
  3. 与冒泡排序区别：选择是选最值后交换，冒泡是相邻元素不断交换
  4. 每趟只保证一个元素到达最终位置

核心结论 ▾

必背比较次数恒定 $\frac{n(n-1)}{2}$；不稳定；空间 $O(1)$；时间 $O(n^2)$；每趟交换一次；堆排序是其改进版，适合交换代价大的场景。

记忆卡片 ▾

比较次数是多少？与序列有关吗？
始终 $\frac{n(n-1)}{2}$，与初始序列无关。
为什么不稳定？
交换可能改变相等元素相对顺序（如 {5,8,5*,2}）。
与插入排序区别？
选择是选最值后一次性交换；插入是移动元素。
和冒泡比较次数区别？
选择恒定 $\frac{n(n-1)}{2}$；冒泡最好仅 $n-1$。

交互动画 · 选择排序逐趟 ▾

点击「下一趟」执行一次选择 + 交换

相关知识点

（暂无关联知识点）