标签题目
排序算法相关面试题
手写快排及复杂度分析
这题不是只问快排定义，而是要求候选人能现场写出可运行的原地分区递归，并解释为什么平均 O(nlogn)、最坏 O(n²)、递归栈平均 O(logn)。高质量回答要把 partition 不变量、递归边界、重复元素处理和 pivot 优化一起讲清楚。
还有哪些 O(nlogn) 的排序算法，各自的原理和使用场景？
这题考察常见 O(nlogn) 比较排序的原理、复杂度、稳定性和场景选择，不能只列名字。
如何合并 N 个有序数组并输出有序数组？
合并 N 个有序数组的经典做法是使用小顶堆维护每个数组当前最小元素，复杂度 O(M log N)，其中 M 是总元素数。
如何实现 NMS 的全过程，包括按 score 排序？
NMS 的流程是按置信度排序，依次保留最高分框，计算它与剩余框的 IoU，并删除重叠过高的候选框，直到候选框处理完。
快排与归并排序的区别？
快排与归并排序的区别？这道腾讯牛客题的关键是围绕“快速排序与归并排序对比”讲清概念、机制、取舍和边界。快速排序和归并排序都能做到平均 O(n log n)，但思路和工程取舍不同。快排通过 partition 原地划分再递归子区间，平均快、缓存友好但通常不稳定，最坏可能 O(n^2)；归并排序先递归拆分再合并有序段，稳定且最坏 O(n log n)，但通常需要 O(n) 额外空间。
当文件无法一次全部加载内存时，如何对大文件内容排序？
当文件无法一次全部加载内存时，如何对大文件内容排序？这道腾讯牛客题的关键是围绕“大文件外部排序”讲清概念、机制、取舍和边界。大文件无法一次加载内存时，用外部排序：按内存上限分块读取，每块在内存中排序后写成临时有序 run，再用 k 路归并把多个有序 run 合成最终有序文件。
快速排序的过程、时间复杂度和常见优化方式是什么？
快速排序的过程、时间复杂度和常见优化方式是什么？这道腾讯牛客题的关键是围绕“快速排序流程与优化”讲清概念、机制、取舍和边界。快速排序的过程是选 pivot，执行 partition，把小于 pivot 的元素放左侧、大于 pivot 的元素放右侧，然后递归排序左右子区间。平均时间 O(n log n)，最坏 O(n^2)，递归栈平均 O(log n)。
常见排序算法中哪些是稳定排序？
常见排序算法中哪些是稳定排序？这道腾讯牛客题的关键是围绕“排序稳定性”讲清概念、机制、取舍和边界。排序稳定性指相等 key 的元素在排序后仍保持原来的相对顺序。常见稳定排序包括冒泡排序、插入排序、归并排序、计数排序、基数排序和桶排序的稳定实现；常见不稳定排序包括快速排序、堆排序、选择排序和希尔排序。