选择排序（Selection Sort）的策略最「朴素」：每一轮从未排序区间里选出最小的元素，直接放到未排序区间的开头，已排序前缀就增长一格。它不像冒泡那样频繁交换——每轮只在最后做至多一次交换。
对长度为 n 的序列，执行过程是：
a[0..n]，记录最小值下标 min_idx，若最小值不在头部就与 a[0] 交换；a[1..n] 重复，把次小值换到下标 1；柱子颜色就是状态语言（页面右侧也有图例）：
a[min_idx]——扫描过程中它会不断被更小的元素取代；a[i] 交换的一对元素；a[0..i]，从左往右生长；动画下方有一行实时解说（如 第 2 轮：扫描 a[3..] 找最小，a[3] = 9 与当前最小 a[0] = 38 比较、本轮最小 a[1] = 17，与 a[0] = 38 交换），结束时汇总总比较次数与交换次数。可以直观看到它的特点：比较次数很多（每轮扫完全程）、交换次数极少（每轮至多 1 次）——这正是它与冒泡排序最大的区别。
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 平均/最坏/最好时间 | O(n²) | 无论输入是否有序，比较次数固定为 n(n-1)/2 |
| 空间 | O(1) | 只需记录最小值下标，原地排序 |
| 交换次数 | 最多 n-1 次 | 若「写入」代价远高于「比较」（如闪存场景），这是它的独特优势 |
| 稳定性 | 不稳定 | 跨距离交换会把相等元素的相对次序打乱（如 [2₁, 2₂, 1] 一轮就变 [1, 2₂, 2₁]） |
#include <iostream>
#include <vector>
#include <utility> // std::swap
using namespace std;
// 选择排序：每轮选出未排序区间的最小值放到 a[i]
void selectionSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (a[j] < a[minIdx]) minIdx = j; // 记录更小值的下标
}
if (minIdx != i) swap(a[i], a[minIdx]); // 每轮至多交换一次
}
}
int main() {
vector<int> a = {5, 2, 9, 1, 7, 3, 8, 4};
selectionSort(a);
for (int x : a) cout << x << ' '; // 输出：1 2 3 4 5 7 8 9
cout << endl;
return 0;
}
选择排序比较次数恒为 O(n²)，且不稳定，通用场景不如插入排序。但它的交换次数是所有朴素排序里最少的（至多 n-1 次），在「比较便宜、写入昂贵」的存储介质上反而占优；「每轮选一个最值」的框架也是优先队列 / 堆排序思想的雏形，CSP-J 阶段常以「每次取最小」「约瑟夫式挑选」等模拟题形式出现。