简单排序 · 选择
选择排序 图解题解
这道题到底在问什么
把数组分成"已排序"和"未排序"两段。每趟在未排序段里找最小值，和未排序段的第一个交换。
- 输入
- [5, 2, 4, 1, 3]
- 输出
- [1, 2, 3, 4, 5]
最优解：一步一步想明白
- 3选择排序慢在哪？它没有"提前结束"的机会：哪怕数组本来就有序，每一趟也得把未排序区从头扫到尾才能确认最小值。比较次数固定是 n²/2，省不掉。
- 4第 i 趟开始前，下标 0..i-1 已经是整个数组里最小的 i 个数、且排好序。所以第 i 趟只要在剩下的未排序区找最小值，换到下标 i，前缀就又长一格——这个不变量是选择排序成立的根。
- 5i=0 min=0第 1 趟从下标 0 开始。先假设当前位 5 就是未排序区最小值（min 记在下标 0），再往右逐个比对。
- 6i=0 min=1拿下标 1 的 2 和当前最小 5 比：2 小于 5，更新 min 到下标 1。
- 7i=0 min=1再看下标 2 的 4：4 大于 2，不是更小，min 不动。这就是一次"比较后发现不需要更新"的负例——大多数比较其实都走这条分支。
- 8i=0 min=3下标 3 的 1 小于 2，更新 min 到下标 3。
- 9i=0 min=3最后下标 4 的 3 大于 1，min 仍是下标 3。整趟扫完，确认未排序区最小值是 1。
- 10swap(0,3)把下标 0 的 5 和最小值 1 交换。1 归位，已排序前缀 = [1]。注意整趟只交换了这一次——这正是选择排序相比冒泡的特点：交换次数最少。
- 11i=1 min=1第 2 趟从下标 1 开始，未排序区 [2,4,5,3] 扫一遍：最小是 2，正好已经在下标 1。
- 12i=1 min=1最小值就在原位，无需真正移动（代码里是和自己交换）。2 归位，前缀扩到 [1,2]。
- 13i=2 swap(2,4)未排序区 [4,5,3] 扫一遍最小是 3（在下标 4），和下标 2 交换。3 归位，前缀 [1,2,3]。
- 14i=3 swap(3,4)未排序区 [5,4] 最小是 4，和下标 3 交换。4 归位。
- 15done只剩一个 5 时它必然已是最大、自动落在末位，所以外层只需跑到倒数第二个。整个数组 [1,2,3,4,5] 有序。
- 18选择排序的思路是"为每个空位选对的数"，冒泡是"让对的数自己浮上去"。同为 O(n²)，但选择的交换更省。它和堆排序同源——堆排是用堆在 O(log n) 内更快地选出最大。
⚠️ 容易写错的地方
✗ 错：边扫边交换：a[j] < a[i] 就立刻 swap
✓ 对：先找到 min_idx，整趟扫完只交换一次
边扫边换会做大量无用交换，违背选择排序"换得最少"的初衷，还会破坏稳定性
✗ 错：内层 for j in range(i, n)
✓ 对：range(i + 1, n)
i 本身就是 min_idx 的初值，从 i 比起是和自己比，多余
完整代码（Python）
Python
n = len(nums)
for i in range(n - 1): # i 是当前要填的空位
min_idx = i # 先假设当前位最小
for j in range(i + 1, n): # 在未排序区找更小
if nums[j] < nums[min_idx]: # 更小才更新下标
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i] # 每趟只换一次套路模板 · 选择排序（背下来）
for i in range(n - 1):
m = i
for j in range(i + 1, n):
if a[j] < a[m]: m = j # 记最小下标
a[i], a[m] = a[m], a[i] # 一趟一次交换复杂度
时间复杂度
O(n²)
两层循环，比较 n(n-1)/2 次，与初始顺序无关
空间复杂度
O(1)
只在原数组上交换，不开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 选择排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「选择」，换最直接的暴力解会差在哪？+
选择抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。