手写实现一种数组排序算法
哪些公司问过
答案要点
- 快排:选基准、一趟划分、递归左右两段,平均 O(n log n),最坏 O(n²)
- 基准随机化或三数取中,重复元素多时用三路划分
- 归并排序稳定、最坏 O(n log n),需要 O(n) 额外空间
- 堆排序原地、最坏 O(n log n),但不稳定
- 正确处理空数组、单元素、重复元素等边界,并能说出复杂度和稳定性
易错点
- 划分时指针越界或死循环,没处理好与基准相等的元素
- 固定取第一个元素做基准,有序输入下退化为 O(n²)
- 把快排说成稳定排序,或说归并排序是原地排序
面试官常见追问
- 数据基本有序时用什么排序?
- 顺便写个二分查找,要注意什么?
- 桶排序适合什么场景?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场