快排与归并排序的区别？｜腾讯 C/C++面经解析

60 秒回答模板

可以这样回答：快速排序和归并排序都能做到平均 O(n log n)，但思路和工程取舍不同。快排通过 partition 原地划分再递归子区间，平均快、缓存友好但通常不稳定，最坏可能 O(n^2)；归并排序先递归拆分再合并有序段，稳定且最坏 O(n log n)，但通常需要 O(n) 额外空间。快排选 pivot，把小于和大于 pivot 的元素分到两侧，pivot 到位后递归左右区间；归并排序把数组拆到小段，再用双指针合并两个有序段。链表或外部排序场景下归并更自然，数组内存排序常用快排或 introsort 变体。快排空间通常 O(log n) 递归栈，局部性好但受 pivot 选择影响；归并排序稳定、顺序读写友好，适合链表和外部排序，但数组上额外空间成本明显。不要只比较复杂度。要补稳定性、原地性、最坏情况、pivot 优化、额外空间、链表/外部排序适配和重复元素三路切分。验证时重点看：看 partition 是否正确、归并合并是否稳定、重复元素、逆序输入、递归深度、额外空间和相等 key 顺序。

考点 考点边界

主线 核心机制

易错点 只背快排和归并都是 O(n log n)，没有比较稳定…

深入解析

考点边界

这题必须围绕“快速排序与归并排序对比”本身回答，不能套相邻大类模板。先给定义或目标，再展开机制、边界、取舍和验证抓手。回答时要主动点出题面关键词对应的对象、输入输出和约束条件，避免把具体问题讲成宽泛复习提纲。本题对应“快速排序与归并排序对比”，核心前提是：快速排序和归并排序都能做到平均 O(n log n)，但思路和工程取舍不同。快排通过 partition 原地划分再递归子区间，平均快、缓存友好但通常不稳定，最坏可能 O(n^2)；归并排序先递归拆分再合并有序段，稳定且最坏 O(n log n)，但通常需要 O(n) 额外空间。

核心机制

快排选 pivot，把小于和大于 pivot 的元素分到两侧，pivot 到位后递归左右区间；归并排序把数组拆到小段，再用双指针合并两个有序段。链表或外部排序场景下归并更自然，数组内存排序常用快排或 introsort 变体。关键证据要落到状态转移、不变量、边界用例、复杂度来源，这样才能说明机制为什么能支撑题目结论。如果继续展开，要说清状态定义、不变量、边界更新、终止条件和复杂度来源，并用反例说明为什么相邻做法不成立。

关键取舍

快排空间通常 O(log n) 递归栈，局部性好但受 pivot 选择影响；归并排序稳定、顺序读写友好，适合链表和外部排序，但数组上额外空间成本明显。因此要用输入规模、额外空间、最坏复杂度和边界用例来决定方案，而不是只背一个平均复杂度。这些取舍决定了方案在不同输入规模、延迟、内存、并发、泛化或一致性要求下是否仍然成立。

边界风险

不要只比较复杂度。要补稳定性、原地性、最坏情况、pivot 优化、额外空间、链表/外部排序适配和重复元素三路切分。排查时优先用空输入、重复值、极端有序数据、溢出、内存上限和复杂度退化样例验证。需要特别关注极端输入、数据分布变化、资源不足、并发竞争或观测口径错误带来的退化。修复时要用最小反例复现错误，再检查边界条件、循环不变量、数据结构选择和复杂度退化点。

验证抓手

验证时要覆盖空输入、单元素、重复元素、边界溢出、极端有序或逆序数据，并明确时间复杂度和空间复杂度。能说出为什么这个复杂度成立，比只写伪代码更可靠。针对本题，最有价值的验证信号是：看 partition 是否正确、归并合并是否稳定、重复元素、逆序输入、递归深度、额外空间和相等 key 顺序。把验证抓手说出来，可以让答案从知识点延伸到算法正确性、复杂度和边界用例验证。

易错点

只背快排和归并都是 O(n log n)，没有比较稳定性、额外空间、最坏情况和缓存局部性。
把快排说成一定最快，忽略 pivot 选择差时退化以及递归深度风险。
只背“快速排序与归并排序对比”的结论，漏掉关键步骤：快排选 pivot，把小于和大于 pivot 的元素分到两侧，pivot 到位后递归左右区间；归并排序把数组拆到小段，再用双指针合并两个有序段。链表或外部排序场景下归并更自然，数组内存排序常用快排或 introsort 变体。
没有说明“快速排序与归并排序对比”的失败边界：不要只比较复杂度。要补稳定性、原地性、最坏情况、pivot 优化、额外空间、链表/外部排序适配和重复元素三路切分。
把相邻概念混用，没有明确说明这道题真正考察的边界。
没有给出验证方式，导致答案听起来完整但无法判断是否真的生效。

面试官追问

快排和归并排序在稳定性与空间上怎么对比？

快排通常原地划分，平均快且缓存友好，但不稳定，pivot 选择差会退化到 O(n^2)；归并排序稳定且最坏 O(n log n)，但通常需要 O(n) 额外空间。

什么场景更适合归并排序而不是快排？

需要稳定排序、链表排序、外部排序或最坏复杂度稳定时，归并更合适。内存紧张且数据在数组中、追求平均性能时，快排更常见，因此要把稳定性和空间成本一起说清楚。

“快速排序与归并排序对比”追问实现细节时，应该展开哪条链路？

快速排序和归并排序都能做到平均 O(n log n)，但思路和工程取舍不同。快排通过 partition 原地划分再递归子区间，平均快、缓存友好但通常不稳定，最坏可能 O(n^2)；归并排序先递归拆分再合并有序段，稳定且最坏 O(n log n)，但通常需要 O(n) 额外空间。面试官继续追问时，应该沿着这条机制展开：快排选 pivot，把小于和大于 pivot 的元素分到两侧，pivot 到位后递归左右区间；归并排序把数组拆到小段，再用双指针合并两个有序段。链表或外部排序场景下归并更自然，数组内存排序常用快排或 introsort 变体。

“快速排序与归并排序对比”怎么验证结论没有答偏？

优先给出能观察或推导的证据：看 partition 是否正确、归并合并是否稳定、重复元素、逆序输入、递归深度、额外空间和相等 key 顺序。同时补充失败边界：不要只比较复杂度。要补稳定性、原地性、最坏情况、pivot 优化、额外空间、链表/外部排序适配和重复元素三路切分。

“快排与归并排序的区别”继续追问时最该补哪条边界？

应该围绕“快速排序与归并排序对比”补适用前提、失败场景和验证证据。先说明哪些条件下这个机制成立，再说明哪些输入规模、并发状态、数据分布或资源限制会让答案需要调整。