手写选择排序
哪些公司问过
海信1招银网络科技1
答案要点
- 每轮在未排序区间找最小值,与未排序区间首元素交换,已排序区间加一
- 外层 i 从 0 到 n-2,内层 j 从 i+1 开始找 minIdx,minIdx≠i 时交换
- 比较次数固定为 n(n-1)/2,最好最坏平均时间都是 O(n²),空间 O(1)
- 交换次数最多 n-1 次,适合写操作代价高的场景
- 选择排序不稳定,远距离交换会打乱相等元素的相对顺序
易错点
- 说选择排序是稳定排序
- 以为有序输入时选择排序是 O(n),实际比较次数不变
- 同时找最大最小时没处理最大值恰好在位置 i 被换走的情况
面试官常见追问
- 选择排序能改成稳定的吗?
- 选择排序和冒泡、插入排序怎么比较?
- 有什么优化思路?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场