01

60 秒回答模板

常见 O(nlogn) 排序有快速排序、归并排序、堆排序，很多语言内置排序还会用 TimSort 或混合排序。快排通过 partition 分治，平均 O(nlogn)、原地、缓存友好，但不稳定且最坏 O(n²)，适合内存数组的通用排序。归并排序通过先分再合并，时间稳定 O(nlogn)、稳定，适合链表、外部排序和需要稳定性的场景，但数组归并通常要 O(n) 额外空间。堆排序用堆反复取最大或最小，原地且最坏 O(nlogn)，但不稳定、常数和缓存局部性一般，更常用于 TopK 或需要最坏复杂度兜底的场景。选择时要看数据规模、是否稳定、内存限制、输入分布和是否在磁盘上。

考点 先说明比较排序下界
主线 快排重在 partition
易错点 只列快排、归并、堆排名字，不比较时间、空间、稳定性和适…
02

深入解析

01

先说明比较排序下界

基于比较的通用排序，平均意义上很难突破 O(nlogn)，因为排序结果对应大量排列，比较决策树高度需要 log(n!) 量级。非比较排序如计数、桶、基数排序依赖值域条件，不属于同一类通用比较排序。

02

快排重在 partition

快排选 pivot，把数组分成小于和大于 pivot 的两部分再递归。它平均性能好、常数小、原地、缓存友好，但 pivot 极端时会退化到 O(n²)，通常用随机 pivot、三数取中和三路分区缓解。

03

归并重在稳定合并

归并排序递归拆分后按顺序合并两个有序段。它每层合并 O(n)，层数 O(logn)，最坏也是 O(nlogn)，天然稳定，适合链表排序和外部排序，因为可以顺序读写。

04

堆排重在最坏兜底

堆排序先建堆，再反复把堆顶元素交换到尾部并下沉调整。它额外空间 O(1)，最坏 O(nlogn)，但跳跃访问多，缓存局部性不如快排，且不稳定。

05

场景选择要有维度

需要稳定性选归并或稳定混合排序；内存紧张且要原地可考虑快排或堆排；数据在磁盘上优先归并；只要最大/最小 K 个元素常用堆；输入局部有序时内置 TimSort 类算法通常表现更好。

03

易错点

  • 只列快排、归并、堆排名字，不比较时间、空间、稳定性和适用场景。
  • 把快排说成最坏也是 O(nlogn)，忽略固定 pivot 在有序输入上的退化。
  • 认为堆排序因为最坏 O(nlogn) 就一定比快排更快，忽略常数和缓存局部性。
  • 把所有 O(nlogn) 排序都说成稳定，忽略快排和堆排通常不稳定。
04

面试官追问

为什么归并排序稳定？

合并两个有序段时，相等元素优先取前一个有序段里的原有元素，就能保留相等元素的相对顺序。

快排为什么实际常用？

平均性能好，原地排序，常数小，缓存局部性较好。只要通过随机 pivot、三数取中和小数组插入排序等优化，实际表现通常很强。

堆排序为什么不是默认最快？

堆操作需要频繁父子跳转访问，缓存局部性差；相同 O(nlogn) 下常数可能高于优化快排或混合排序。

外部排序为什么常用归并？

外部排序数据放在磁盘，顺序读写比随机访问更友好。归并可以先生成有序段，再多路归并，天然适合磁盘和流式处理。