选择排序 图解题解
这道题到底在问什么
- 输入
- nums = [5,2,4,1,3]
- 输出
- [1,2,3,4,5]（升序）
最优解：一步一步想明白
- 3记住两个角色：i 是当前趟要填的位置（未排序区的开头），min 是这一趟扫到目前为止最小值所在的下标。
- 4一开始整个数组都属于未排序区（右段），左边的已排序区还是空的。我们一趟一趟地把最小值挑到左边。
- 5第 1 趟：要填的位置是下标 0。先假设它自己就是未排序区的最小值，min = 0（值 5），再往右逐个比对。
- 6比下标 1 的值 2 和当前最小 5：2 更小，把 min 改记到下标 1。
- 7比下标 2 的值 4 和当前最小 2：4 不比 2 小，min 保持不变。
- 8比下标 3 的值 1 和当前最小 2：1 更小，把 min 改记到下标 3。
- 9比下标 4 的值 3 和当前最小 1：3 不比 1 小，min 保持不变。
- 10本趟扫完，最小值在下标 3。把它和下标 0 交换，于是下标 0 被填上正确的值 1，已排序区往右扩了一格。
- 11第 2 趟：要填的位置是下标 1。先假设它自己就是未排序区的最小值，min = 1（值 2），再往右逐个比对。
- 12比下标 2 的值 4 和当前最小 2：4 不比 2 小，min 保持不变。
- 13比下标 3 的值 5 和当前最小 2：5 不比 2 小，min 保持不变。
- 14比下标 4 的值 3 和当前最小 2：3 不比 2 小，min 保持不变。
- 15本趟最小值正好就在下标 1，不用交换。下标 1 已经是正确的值 2，已排序区往右扩一格。
- 16第 3 趟：要填的位置是下标 2。先假设它自己就是未排序区的最小值，min = 2（值 4），再往右逐个比对。
- 17比下标 3 的值 5 和当前最小 4：5 不比 4 小，min 保持不变。
- 18比下标 4 的值 3 和当前最小 4：3 更小，把 min 改记到下标 4。
- 19本趟扫完，最小值在下标 4。把它和下标 2 交换，于是下标 2 被填上正确的值 3，已排序区往右扩了一格。
- 20第 4 趟：要填的位置是下标 3。先假设它自己就是未排序区的最小值，min = 3（值 5），再往右逐个比对。
- 21比下标 4 的值 4 和当前最小 5：4 更小，把 min 改记到下标 4。
- 22本趟扫完，最小值在下标 4。把它和下标 3 交换，于是下标 3 被填上正确的值 4，已排序区往右扩了一格。
- 23最后一格（下标 4）自然就是剩下唯一的数，无需再比。整个数组从小到大排好了：1，2，3，4，5。
⚠️ 容易写错的地方
✗ 错：内层比较时拿 nums[j] 和 nums[i] 比
✓ 对：和当前最小 nums[min_i] 比
要找的是整段的最小值，比较基准应一直是已记下的最小值，而不是固定的 i 处
✗ 错：每遇到更小的就立刻交换
✓ 对：先只更新 min_i，扫完一趟再交换一次
边扫边换会做大量无用交换，丢掉选择排序「交换次数少」的核心优点
✗ 错：外层循环写成 range(n)
✓ 对：range(n-1) 即可
前 n-1 个都填对后，最后一个自然就位，多扫一趟不出错但没必要
完整代码（Python / C++ / Java）
Python
def selection_sort(nums):
n = len(nums)
for i in range(n - 1): # i 是本趟要填的位置
min_i = i # 先假设 i 处最小
for j in range(i + 1, n):
if nums[j] < nums[min_i]:
min_i = j # 记下更小的下标
nums[i], nums[min_i] = nums[min_i], nums[i] # 换到最前
return numsC++
void selectionSort(vector<int>& nums){
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
int minI = i;
for (int j = i + 1; j < n; j++)
if (nums[j] < nums[minI]) minI = j;
swap(nums[i], nums[minI]);
}
}Java
void selectionSort(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
int minI = i;
for (int j = i + 1; j < n; j++)
if (nums[j] < nums[minI]) minI = j;
int t = nums[i]; nums[i] = nums[minI]; nums[minI] = t;
}
}复杂度
时间
O(n²)
两层循环，比较次数约 n(n-1)/2，和数据是否有序无关
空间
O(1)
只用 min_i 一个下标和一次交换的临时变量，原地排序
交换
O(n)
每趟最多换一次，总交换次数最多 n-1，是它相对冒泡的优点
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 选择排序 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
选择排序和冒泡排序最大的区别是什么？+
两者比较次数都是 O(n²)，但选择排序每趟最多交换一次（总共最多 n-1 次），冒泡可能每趟换很多次。所以当「交换/写入」代价高时，选择排序更划算。
选择排序是稳定排序吗？+
不是。交换会把相等元素的相对顺序打乱，比如 [5,5,2] 第一趟会把前面的 5 和 2 交换，两个 5 的先后就变了。
它的时间复杂度会因为数组本来有序而变好吗？+
不会。无论数据是否有序，内层都要完整扫一遍找最小值，比较次数恒为 n(n-1)/2，始终是 O(n²)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 选择排序 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。