归并排序及其时间复杂度推导
哪些公司问过
答案要点
- 分治:对半拆分、递归排序、合并两个有序子数组
- 合并用双指针,相等时取左侧元素,保证稳定
- 递推式 T(n)=2T(n/2)+O(n)
- 递归树共 log n 层,每层合并总代价 O(n),总计 O(n log 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 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场