选择排序的核心逻辑是每轮在未排序部分选出最小（或最大）元素，与当前待填位置直接交换。其比较次数固定为n(n-1)/2，交换最多n−1次，原地、不稳定，适合交换开销大或写入敏感场景。
选择排序的核心逻辑是什么
选择排序不是靠交换相邻元素，而是每轮找剩余未排序部分的最小（或最大）值，把它和当前待填位置直接交换。关键在“选”不在“冒”，所以比较次数固定为 n*(n-1)/2，但交换次数最多只有 n-1 次——这对写入敏感场景（比如某些嵌入式存储）有实际意义。
- 每轮只做一次交换，适合交换开销大的对象（如大结构体）
- 不稳定：相同值的相对顺序可能改变，比如
{5, 8, 5, 2}中两个5的位置会变 - 原地排序，仅需
O(1)额外空间
标准 C++ 实现要注意的三个细节
写一个通用、安全、符合习惯的版本，得避开几个典型坑：
- 循环边界容易错：内层找最小值的范围是
[i, n-1]，不是[i+1, n-1]（否则漏掉i位置自己） - 索引初始化必须设为
i，不能设为0或1，否则第一轮就崩 - 交换前要判断
min_idx != i，避免自交换（虽不影响结果，但可能触发无谓的赋值或移动构造）
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int min_idx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
std::swap(arr[i], arr[min_idx]);
}
}
}怎么改成支持任意类型和自定义比较
用模板 + 比较器，就能复用到 std::string、自定义类甚至指针数组：
- 类型参数
T要求支持operator<，或传入显式比较函数 - 使用
std::iter_swap替代std::swap更通用（适配迭代器） - 注意比较器默认用
std::less<T>{}，别直接写<运算符
template <typename Iterator, typename Compare = std::less<typename std::iterator_traits<Iterator>::value_type>>
void selectionSort(Iterator first, Iterator last, Compare comp = {}) {
for (auto it = first; it != last; ++it) {
auto min_it = it;
for (auto jt = std::next(it); jt != last; ++jt) {
if (comp(*jt, *min_it)) {
min_it = jt;
}
}
if (min_it != it) {
std::iter_swap(it, min_it);
}
}
}为什么不用 std::sort 而手写选择排序
除非教学、面试、或极特殊约束，否则真没必要手写。常见误用场景包括：
立即学习“C++免费学习笔记（深入）”；
- 以为它比
std::sort“更简单所以更快”：实际std::sort是混合快排/堆排/插入排序，O(n log n)，而选择排序恒为O(n²) - 在线数据流里误以为能边读边排：选择排序必须知道全部元素才能开始第一轮，不支持增量
- 用它替代
std::nth_element找第 k 小：后者是O(n)，选择排序找最小值都要O(n)，找第 k 小得跑 k 轮，退化成O(kn)
真正值得手写的时刻很少：比如裸机环境没 STL、调试教学演示、或实现某种受限变体（如只允许交换到末尾）。其他时候，写错一个索引，花十分钟调，不如直接敲 std::sort。
