Appearance
简单选择排序
为什么需要简单选择排序
冒泡排序每发现一对逆序就要做一次交换，交换次数较多。能不能每一轮只做一次交换，把最小的元素直接放到最终位置？简单选择排序正是基于这个思路：每轮从未排序部分选出最小元素，与未排序部分的第一个元素交换，从而将交换次数降到最低。
408 考研中，简单选择排序是选择类排序的基础，也是理解堆排序的前置知识。它的比较次数固定、不受输入数据影响这一特点，是选择题的常见考点。
核心思想
简单选择排序的核心操作：
- 选最小：在未排序区间
[i, n-1]中找到最小元素的下标min - 交换归位：将
a[min]与a[i]交换，a[i]就到达最终位置 - 缩小范围：
i++，未排序区间缩小一个元素，重复上述过程
每完成一轮，已排序区间增加一个元素，未排序区间减少一个元素。共需 n-1 轮即可完成排序。
第0轮: [待排序区间 ——————————————————]
第1轮: [已排序] [待排序区间 ——————————]
第2轮: [已排序——] [待排序区间 ————————]
...
第n-2轮: [已排序————————————————] [待排]交互可视化
通过下方的交互动画，你可以逐步观察简单选择排序的执行过程：
操作详解
算法思路
关键步骤：
- 外层循环
i从0到n-2，表示当前要确定的位置 - 内层循环在
[i, n-1]中找最小元素的下标min - 若
min != i，交换a[i]与a[min] - 重复直到所有位置确定
c
void SelectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min])
min = j;
}
if (min != i) {
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}
}排序过程详解
以数组 {3, 1, 4, 1, 5} 为例，演示完整排序过程：
| 轮次 | 未排序区间 | 找到最小值 | 交换操作 | 数组状态 |
|---|---|---|---|---|
| 初始 | — | — | — | {3, 1, 4, 1, 5} |
| 第1轮 | [0, 4] | a[1]=1 | a[0]↔a[1] | {1, 3, 4, 1, 5} |
| 第2轮 | [1, 4] | a[3]=1 | a[1]↔a[3] | {1, 1, 4, 3, 5} |
| 第3轮 | [2, 4] | a[3]=3 | a[2]↔a[3] | {1, 1, 3, 4, 5} |
| 第4轮 | [3, 4] | a[3]=4 | 无需交换 | {1, 1, 3, 4, 5} |
共进行 4 轮（n-1 轮），每轮在未排序区间扫描一遍找最小值，最多做 1 次交换。
不稳定性分析
简单选择排序是不稳定的排序算法。
经典反例：{2, 2, 1}（用下标区分两个 2：2₁, 2₂, 1）
| 轮次 | 操作 | 结果 |
|---|---|---|
| 初始 | — | {2₁, 2₂, 1} |
| 第1轮 | 最小值为 1，a[0]↔a[2] | {1, 2₂, 2₁} |
排序后 2₂ 排在 2₁ 前面，两个相等元素的相对顺序发生了改变，因此不稳定。
根本原因：交换操作会把 a[i] 直接甩到后面的位置，跨越了中间与它相等的元素。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 比较次数 | n(n-1)/2 | 与初始序列无关，始终为 O(n²) |
| 最好交换次数 | 0 | 已有序，无需交换 |
| 最坏交换次数 | n-1 | 每轮都需交换 |
| 时间复杂度（所有情况） | O(n²) | 比较次数固定，不随输入变化 |
| 空间复杂度 | O(1) | 仅需常数级辅助变量 |
| 稳定性 | 不稳定 | 反例：{2, 2, 1} |
与冒泡排序的对比：
| 对比项 | 简单选择排序 | 冒泡排序 |
|---|---|---|
| 比较次数 | 固定 n(n-1)/2 | 最好 O(n)，最坏 O(n²) |
| 交换次数 | 最多 n-1 次 | 最坏 O(n²) 次 |
| 对输入敏感 | 否（比较次数不变） | 是（有序时可提前终止） |
| 稳定性 | 不稳定 | 稳定 |
| 空间复杂度 | O(1) | O(1) |
简单选择排序的优势在于交换次数少（每轮最多 1 次），当数据交换代价较大时优于冒泡排序。
考研高频考点
- ⭐ 比较次数始终为 n(n-1)/2，与初始序列无关（选择题高频）
- ⭐ 不稳定排序，能用 {2, 2, 1} 举反例（选择题/简答题必考）
- ⭐ 时间复杂度始终 O(n²)，不存在"最好 O(n)"的情况（易与冒泡混淆）
- ⭐ 与冒泡排序的对比：交换次数、稳定性、对输入的敏感性（简答题）
- 交换次数最多 n-1 次，远少于冒泡排序（偶尔考）
- 简单选择排序是堆排序的基础思想（理解题）