选择排序Selection sort

每轮从未排序部分选择最小元素放到前端。

核心约束: 已经处理的前缀包含全局最小的若干元素。
适用问题: 理解原地排序与比较 / 交换成本的区别。
边界与取舍: 常规实现不稳定，较大输入很少作为首选。

时间与空间#

n 为元素数；每轮在剩余元素中选择最小值。

时间复杂度: 最好 / 平均 / 最坏 $O(n^{2})$ 次比较
辅助空间: $O(1)$

标准交换式实现仅 $O(n)$ 次交换，但通常不稳定。输入已排序也不会免去逐轮寻找最小值的比较。

基础原理参考资料

Princeton · Selection选择排序的循环实现及其比较、交换行为。