选择排序的核心逻辑是每轮在未排序部分找最小（或最大）值并与当前首位交换，本质为“挑出最值+归位”，不依赖相邻比较，无法提前终止，时间复杂度恒为O(n²)。
选择排序的核心逻辑是什么
选择排序不依赖相邻元素比较，而是每轮在未排序部分找最小（或最大）值，和当前首位交换。它本质是“挑出最值 + 归位”，不是“冒泡式交换”。这意味着即使数组已有序，std::swap 仍会执行 n-1 次（除最后一轮），这是它无法提前终止的根本原因。
标准实现中容易写错的边界和索引
常见错误集中在内层循环起始位置和比较范围。未排序区从 i 开始，所以内层必须从 i+1 开始遍历；若写成 j = i，会导致自己和自己比，min_idx 初始设为 i 就失效。
void selectionSort(std::vector& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { int min_idx = i; // 当前假设最小值在位置 i for (int j = i + 1; j < n; ++j) { // 注意：j 从 i+1 开始 if (arr[j] < arr[min_idx]) { min_idx = j; } } if (min_idx != i) { // 避免自交换 std::swap(arr[i], arr[min_idx]); } } }
为什么选择排序不稳定且不适合大数据量
稳定性被破坏是因为交换可能跨过相等元素：比如序列 [5, 2a, 8, 2b]，第一轮把 2a 换到索引 0，2b 被后移，相对顺序就变了。时间复杂度恒为 O(n²)，无论最好/最坏情况；比较次数固定为 n(n−1)/2，但交换最多仅 n−1 次——这在写入敏感场景（如 flash 存储模拟）反而是优势。
- 不支持随机访问优化（不像快排可选 pivot）
- 缓存局部性差：每次找最小值要遍历剩余段，cache line 反复丢弃
- STL 中无对应算法，
std::sort是 introsort，勿误用
如何验证你的选择排序是否正确
重点检查三类边界输入：空数组、单元素、全相同值。尤其注意全相同值时是否发生多余交换（应有 if (min_idx != i) 守护）。调试时可在内层循环加日志输出 i、min_idx 和交换前后子数组，但正式代码务必删掉。
立即学习“C++免费学习笔记（深入）”；
一个易忽略的点：如果用 int 下标处理 size_t 大小的容器（如 std::vector::size()），当 n == 0 时 n-1 会变成极大正数，导致死循环——务必统一用 size_t 或加 if (n == 0) return; 防御。
