设计最快的考研分数排序算法
哪些公司问过
答案要点
- 背景问题如实简短回答,重点讲算法
- 分数是范围有限的整数,计数排序 O(n + k) 时间、O(k) 空间
- 带考生记录时用前缀和加从后往前放置,保证稳定
- 小数分数可放大为整数;范围很大时用基数排序或桶排序
- n 大、k 小时优于比较排序的 O(n log n)
易错点
- 直接说快速排序最快,忽略分数范围有限的特点
- 计数排序带记录时没有处理稳定性
- 分数范围很大时仍用计数排序,空间浪费
面试官常见追问
- 为什么比较排序不能低于 O(n log n)?
- 几百万考生的分数排名怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场