选择排序的核心逻辑是每轮在未排序部分选出最小（或最大）元素，与当前待填位置直接交换。其比较次数固定为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 <h3>怎么改成支持任意类型和自定义比较</h3>
<p>用模板 + 比较器，就能复用到 <code>std::string</code>、自定义类甚至指针数组：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>类型参数 <code>T</code> 要求支持 <code>operator，或传入显式比较函数</code>
</li>
<li>使用 <code>std::iter_swap</code> 替代 <code>std::swap</code> 更通用（适配迭代器）</li>
<li>注意比较器默认用 <code>std::less<t>{}</t></code>，别直接写 <code> 运算符</code>
</li>
</ul>
<pre class="brush:php;toolbar:false;">template <typename iterator typename compare="std::less<typename" std::iterator_traits>::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);
}
}
}</typename>
为什么不用 std::sort 而手写选择排序
除非教学、面试、或极特殊约束，否则真没必要手写。常见误用场景包括：
- 以为它比
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。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
