题目描述
把数组分成"已排序"和"未排序"两段。每趟在未排序段里找最小值，和未排序段的第一个交换。
思路解析
选择排序慢在哪？它没有"提前结束"的机会：哪怕数组本来就有序，每一趟也得把未排序区从头扫到尾才能确认最小值。比较次数固定是 n²/2，省不掉。
第 i 趟开始前，下标 0..i-1 已经是整个数组里最小的 i 个数、且排好序。所以第 i 趟只要在剩下的未排序区找最小值，换到下标 i，前缀就又长一格——这个不变量是选择排序成立的根。
第 1 趟 · 假设 5 最小：第 1 趟从下标 0 开始。先假设当前位 5 就是未排序区最小值（min 记在下标 0），再往右逐个比对。
比 5 和 2 · 2 更小：拿下标 1 的 2 和当前最小 5 比：2 小于 5，更新 min 到下标 1。
比 4 和 2 · 不更新：再看下标 2 的 4：4 大于 2，不是更小，min 不动。这就是一次"比较后发现不需要更新"的负例——大多数比较其实都走这条分支。
比 1 和 2 · 1 更小：下标 3 的 1 小于 2，更新 min 到下标 3。
比 3 和 1 · 不更新：最后下标 4 的 3 大于 1，min 仍是下标 3。整趟扫完，确认未排序区最小值是 1。
第 1 趟 · 把 1 换到最前：把下标 0 的 5 和最小值 1 交换。1 归位，已排序前缀 = [1]。注意整趟只交换了这一次——这正是选择排序相比冒泡的特点：交换次数最少。
第 2 趟 · 在 [2,4,5,3] 找最小：第 2 趟从下标 1 开始，未排序区 [2,4,5,3] 扫一遍：最小是 2，正好已经在下标 1。
第 2 趟 · 自己换自己：最小值就在原位，无需真正移动（代码里是和自己交换）。2 归位，前缀扩到 [1,2]。
第 3 趟 · 最小 3 换上来：未排序区 [4,5,3] 扫一遍最小是 3（在下标 4），和下标 2 交换。3 归位，前缀 [1,2,3]。
第 4 趟 · 4 换到位：未排序区 [5,4] 最小是 4，和下标 3 交换。4 归位。
收尾 · 最后一个自动到位：只剩一个 5 时它必然已是最大、自动落在末位，所以外层只需跑到倒数第二个。整个数组 [1,2,3,4,5] 有序。
选择排序的思路是"为每个空位选对的数"，冒泡是"让对的数自己浮上去"。同为 O(n²)，但选择的交换更省。它和堆排序同源——堆排是用堆在 O(log n) 内更快地选出最大。
参考代码（Python）
1n = len(nums)
2for i in range(n - 1): # i 是当前要填的空位
3 min_idx = i # 先假设当前位最小
4 for j in range(i + 1, n): # 在未排序区找更小
5 if nums[j] < nums[min_idx]: # 更小才更新下标
6 min_idx = j
7 nums[i], nums[min_idx] = nums[min_idx], nums[i] # 每趟只换一次复杂度分析
- 时间复杂度：O(n²) —— 两层循环，比较 n(n-1)/2 次，与初始顺序无关
- 空间复杂度：O(1) —— 只在原数组上交换，不开额外数组
套路模板
记住骨架：外层定空位、内层找最小下标、末尾一次交换。改成"找最大放末尾"就是另一种写法，思想完全一样。
1for i in range(n - 1):
2 m = i
3 for j in range(i + 1, n):
4 if a[j] < a[m]: m = j # 记最小下标
5 a[i], a[m] = a[m], a[i] # 一趟一次交换易错点
- 错误写法：边扫边交换：a[j] < a[i] 就立刻 swap → 正确写法：先找到 min_idx，整趟扫完只交换一次（边扫边换会做大量无用交换，违背选择排序"换得最少"的初衷，还会破坏稳定性）
- 错误写法：内层 for j in range(i, n) → 正确写法：range(i + 1, n)（i 本身就是 min_idx 的初值，从 i 比起是和自己比，多余）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。