选择排序
从内层循环的每一步比较到交换，带你手推整个排序过程并算清复杂度
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
选择排序
从内层循环的每一步比较到交换，带你手推整个排序过程并算清复杂度
核心构思：选出来放好
打扑克理牌时，你会先把手里最大的那张抽出来，放到最左边；再从剩下的牌里挑最大的，放到它右边。选择排序干的就是这件事：每一轮都「选出最大，放到该放的位置」。
每轮从手里挑出最大的牌，对应每趟从未排序区间选出极值
不变式：前缀已排序
上一页我们把最小的元素「选出来放好」。只选一次还不够——想象一条分界线从左往右爬：线左边永远是排好的，线右边待处理。这条线每走一格，排序就完成一格。
填好的格子对应已排序前缀，空白格对应无序后缀
一趟完整流程分步走
一趟选择排序：扫描、比较、记录、交换，四步环环相扣。
完整实例演示
从上往下看：每趟选最小值换到前缀末尾，灰区（已排序前缀）逐趟变长。
框架实现
看到选择排序的双层循环骨架：外层管趟数，内层找最大，交换一次收尾。
外层 i 是未排序区左边界；内层只记下标不动手；一趟结束后才交换，把最大值放到前缀末尾——与不变式完全对应。
推敲：往哪放、放多少趟
前页框架已能跑通，但有两个细节值得推敲：每趟选出的最大值该放到区间的哪一端？整个过程要跑多少趟才算完？把这两个边界问题想透，代码才不会出错。
每轮选出最高的站到队尾，队尾固定后不再参与，n 人只需 n-1 轮
selectMax() 实现
核心接口落地：返回无序区间中最大元素的位置，为交换做准备。
m 存下标而非元素值，比较用严格大于——这两点决定函数正确性与稳定性边界。
自交换与稳定性推敲
都是每趟选一个元素归位，但“怎么放”藏着一个稳定性陷阱：直接交换会不会打乱相等元素的先后？
- 选中后与端位元素 swap，一步到位
- 远距离交换，可能跨越相等元素
- 不稳定：相等元素相对次序可能颠倒
- 选中后逐个后移，腾位再放入
- 相邻移动，只挤开中间元素
- 稳定：相等元素次序得以保持
性能：比较多、移动少
上一页我们发现：不管数据多乱，每趟都得把剩余元素全扫一遍才能选出最值。这种「不看完不放心」的性格，让比较次数天生固定——而换来的是移动次数极少。
评委必须看完每个候选人，无论谁是热门；但最终只挪一次奖杯
自测：一趟走几步
对 n 个元素做选择排序（每趟从未排序区选出最值放好），以下关于趟数与比较次数的说法，正确的是？
要点收束
- ✓每趟从未排序区选出最值，换到前缀末尾，前缀不变式逐步扩张
- ✓核心动作是比较，交换至多每趟一次，移动次数 O(n)
- ✓选择排序不稳定：远距离交换会打乱相等元素的原有次序
- ✓比较次数固定 n(n-1)/2，与输入是否有序无关
- ✓掌握'选出来放好'的框架，堆排序是它的自然升级
课后思考
先自己想一会儿，再看参考答案——问题值得多想一会。
参考答案从不变式角度推敲：交换只发生在无序后缀内部，前缀元素不受影响。可再想想自交换那种边界情形，不变式是否依然完好。
参考答案往回对比插入排序的稳定思路：不跨越等值元素移动即可。可选链表接尾或整体后移腾位，但移动次数会明显增加，权衡就在这里。
参考答案每趟至多一次交换，总交换次数 O(n)，这是它的看家本领。若比较便宜而写昂贵（如闪存），这个特性就值得认真考虑。