分治算法的应用场景及MySQL filesort
哪些公司问过
答案要点
- 分治:拆成相同结构的子问题,递归求解后合并
- 典型应用:归并排序、快排、二分、Karatsuba 乘法、快速幂、MapReduce
- filesort 在 ORDER BY 用不上索引时触发,使用 sort_buffer_size 大小的缓冲区
- 数据放不下时分块排序写临时文件,再多路归并,属于外部归并排序
- Sort_merge_passes 反映归并轮数,可调缓冲区或加索引优化
易错点
- 认为 filesort 一定是在磁盘上排序,其实数据小时在内存完成
- 把分治和动态规划混为一谈
- 只列算法名,说不出「分」和「合」分别在哪
面试官常见追问
- 如何避免 filesort?
- 分治和动态规划有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场