你有没有这样整理过书架？
扫一眼所有书，找到最矮的那本放到最左边，
再从剩下的里面找最矮的放第二位… 一趟一趟地，每轮只做一件事，在未排序的部分里选一个最小值。
这个过程就是选择排序（Selection Sort） 。
排序的过程中，每轮都从未排序区选一个最小元素，交换到已排序区的末尾。
思路简单到不需要任何花哨技巧，但它的特性（不稳定、比较次数固定）让它在面试和理论分析中经常被拿来当对比基准。
它是什么
核心思想 把数组分成”已排序区”和”未排序区”。
初始时已排序区为空。
每轮在未排序区里找最小元素，直接交换到已排序区的末尾。
重复 n-1 轮后全局有序。
“每次选一个最小的放过去，不关心中间过程，只关心结果。” ， 这就是选择排序的全部逻辑。
伪代码
// 仅为示意
for i = 0 to n-2:
minIdx = i
for j = i+1 to n-1:
if arr[j] < arr[minIdx]:
minIdx = j
if minIdx != i:
swap(arr[i], arr[minIdx])核心就两层循环。
外层控制”当前要填哪个位置”。
内层扫描剩余部分找最小值。
下面用流程图拆解。
工作原理流程图
先看整体骨架（对应伪代码的外层循环）：
flowchart LR
A([开始]) --> B[i = 0]
B --> C{ i < n-1 ? }
C -->|否| Z([结束])
C -->|是| D[在 i..n-1 中找最小值 minIdx]
D --> E{"arr[minIdx] != arr[i] ?"}
E -->|是| F["交换 arr[i] 与 arr[minIdx]"]
E -->|否| G[跳过，无需交换]
F --> H[++i]
G --> H
H --> C再看内层”找最小值”的细节：
flowchart LR
A([开始找最小]) --> B[minIdx = i, j = i+1]
B --> C{ j < n ? }
C -->|否| D([返回 minIdx])
C -->|是| E{"arr[j] < arr[minIdx] ?"}
E -->|是| F[minIdx = j]
E -->|否| G[不变]
F --> H[++j]
G --> H
H --> C逐趟演示
用 [5, 3, 8, 4, 2] 跑一遍，看每轮发生了什么：
初始数组: [5, 3, 8, 4, 2]
第 1 趟 (选最小放位置 0): [2] [3,8,4,5]
在 [5,3,8,4,2] 中最小值是 2，与位置 0 的 5 交换
第 2 趟 (选最小放位置 1): [2,3] [8,4,5]
在 [3,8,4,5] 中最小值是 3，已经在正确位置
第 3 趟 (选最小放位置 2): [2,3,4] [8,5]
在 [8,4,5] 中最小值是 4，与位置 2 的 8 交换
第 4 趟 (选最小放位置 3): [2,3,4,5] [8]
在 [8,5] 中最小值是 5，与位置 3 的 8 交换
最终结果: [2, 3, 4, 5, 8]注意观察：每轮只发生一次交换（或零次），这是选择排序和冒泡排序最大的行为差异。冒泡可能一轮交换多次，选择每轮最多一次。
能解决什么问题
适用场景
| 场景 | 说明 |
|---|---|
| 教学入门 | 逻辑最直观，代码量最少 |
| 小规模数据（n < 50） | 常数因子小，简单场景可接受 |
| 写操作昂贵（如 EEPROM） | 每轮最多 1 次交换，写入次数最少之一 |
| 数据量极大 | 不推荐，O(n²) 比较太慢 |
| 几乎有序 | 不推荐，比较次数固定，不如插入排序 |
局限性
| 局限 | 说明 |
|---|---|
| 时间 O(n²) | 数据量大时太慢，n=10000 就要约 5000 万次比较 |
| 不稳定 | 相等元素的相对顺序会被改变（下面会演示） |
| 比较次数固定 | 不管输入是否有序，都是 n(n-1)/2 次比较，无法提前退出 |
| 在链表上实现不如数组高效 | 每轮寻找最小值需从头遍历，无法利用缓存局部性，且指针操作较数组下标更繁琐；但并非”不能实现” |
稳定性问题
程序验证
以下数据展示不稳定性的根本原因。
选择排序是不稳定排序。来看反例：
原始: [2a, 2b, 1]
第 1 轮：在 [2a, 2b, 1] 中找最小 → 1（位置 2），与位置 0 的 2a 交换 → [1, 2b, 2a]
两个 2 的相对顺序从 (2a, 2b) 变成了 (2b, 2a)，稳定性被破坏。跨越相等元素的交换直接打乱了原始相对顺序，这是选择排序无法保证稳定性的根本原因。
C++ 实现与复杂度分析
通用实现 可直接复用的代码：
template <typename T>
void selectionSort(std::vector<T>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j)
if (arr[j] < arr[minIdx])
minIdx = j;
if (minIdx != i)
std::swap(arr[i], arr[minIdx]);
}
}支持任意可比较类型，原地排序，空间 O(1)。
时间复杂度怎么算
基本操作是比较（arr[j] < arr[minIdx]）。
外层跑 n-1 轮。
第 i 轮（i 从 0 开始）的内层比较次数 = (n-1) - (i+1) + 1 = n-i-1 次。
总比较次数 = 第 0 轮 + 第 1 轮 + … + 第 n-2 轮
= (n-1) + (n-2) + … + 1
= 等差数列求和 = n(n-1)/2
去系数留主项：O(n²)
关键点：这个次数是固定的，不管输入是否已经有序。
程序也验证了这一点：
| 输入 | 比较 | 交换 |
|---|---|---|
| 已有序 [1,2,3,4,5] | 10 | 0 |
| 完全逆序 [5,4,3,2,1] | 10 | 2 |
n=5 时 n(n-1)/2 = 10，两种情况比较次数完全一样。区别只在交换次数。
| 情况 | 比较次数 | 交换次数 | 时间复杂度 |
|---|---|---|---|
| 最好 | n(n-1)/2 | 0 | O(n²) |
| 最坏 | n(n-1)/2 | n-1 | O(n²) |
| 平均 | n(n-1)/2 | ≈ n/2 | O(n²) |
最坏交换次数 n-1 当且仅当每轮最小值都不在当前位置时才达到；已有序时交换次数为 0。
三种情况时间复杂度全是 O(n²)，这是选择排序的一个显著特征。
空间复杂度怎么算
只用了 i、j、minIdx 和交换临时变量这几个标量，与数据规模 n 无关。
所以空间复杂度 O(1)，原地排序。
总结
- 是什么：每轮从未排序区选最小元素交换到已排序区末尾，重复 n-1 轮。
- 解决什么 / 用在哪：把无序变有序；适合教学、小规模数据、交换成本高的场景。
- 局限：O(n²) 太慢、不稳定、比较次数无法减少（即使已有序也要跑满）。
- 复杂度怎么算：基本操作是比较 → 内层循环次数构成等差数列 → 总计 n(n-1)/2 → O(n²)；空间只看标量变量 → O(1)。三种情况时间复杂度相同是它的一大特点。
- 进阶联想：把”线性扫描找最值”换成二叉堆加速，就是堆排序，同样的选最值思想，换套数据结构，复杂度从 O(n²) 降到 O(n log n)。