数据结构与算法 / 技术文章

快速排序为什么常常比归并排序快

实际开发、竞赛和面试中,快速排序与归并排序都常被归入 O(nlog⁡n)O(n\log n) 排序,但实际运行时间并不相同。本文面向需要理解排序性能的开发者,从分区方式、内存访问、缓存局部性和额外开销拆开比较,读完后你能解释快速排序为什么经常更快,也能判断什么时候归并排序反而更合适。

先看复杂度:为什么同是 O(nlog⁡n)O(n\log n)

快速排序平均情况下的递推关系可以写成:

T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)

因此平均时间复杂度为 O(nlog⁡n)O(n\log n)。归并排序也满足类似的递推关系,所以平均或稳定情况下同样是 O(nlog⁡n)O(n\log n)。

复杂度只描述增长趋势,并没有把所有运行成本都算进去。实际执行时间还受到比较次数、交换次数、内存分配、数据搬运以及 CPU 缓存命中率等因素影响。因此,两个算法拥有相同的大 OO 表达式,并不代表常数成本相同。

快速排序少做了什么

快速排序通常采用原地分区。以数组为例,分区阶段直接在原数组内部移动元素,把小于基准值的元素放到一侧,大于基准值的元素放到另一侧。

归并排序则通常需要额外数组保存归并结果。完成左右两部分排序后,还要重新读取两个有序区间并把元素写入目标缓冲区,再进行必要的数据复制。

可以把一次典型过程简化成:

text
快速排序:比较 → 分区 → 递归处理子区间
归并排序:比较 → 递归处理子区间 → 额外数组归并 → 数据复制

预期结果:快速排序的核心工作更多集中在原数组内部完成,而归并排序需要额外的归并与数据写入。

缓存局部性为什么重要

现代 CPU 不会每次访问数组都直接从主内存读取数据,而是依赖多级缓存。连续访问、局部访问的数据通常更容易留在缓存中。

快速排序的分区操作主要围绕当前数组区间进行,访问模式相对集中。数据量适中时,连续数组元素更容易形成较好的空间局部性。

归并排序在归并阶段需要同时读取两个子区间,并向另一个数组写入结果。虽然它同样拥有良好的顺序访问特征,但额外的写入和数据流转会增加内存带宽压力。

因此可以把性能差异理解为两层:算法复杂度决定数量级,缓存和内存访问决定相同数量级下的常数。

为什么“交换少”不一定是唯一答案

快速排序常被描述成交换元素,但优秀实现并不意味着不断进行昂贵的交换。实际分区实现可以通过保存临时值、使用两个指针或采用三向分区减少不必要的数据移动。

归并排序也并非一定慢。它的顺序读取与顺序写入非常规整,在外部排序、大规模数据流和链表排序等场景中,这种特性反而非常有价值。

所以不能简单归结为“快速排序交换更少”。更准确的说法是:快速排序通常避免了归并阶段额外的辅助数组和第二轮数据整理,因此常数开销较低,但最终表现仍取决于实现与数据分布。

快速排序什么时候会输

快速排序的平均性能很好,但最坏情况下可能退化到 O(n2)O(n^2)。例如每次都选到极差的基准值,使划分结果长期接近 1:(n−1)1:(n-1)。

常见改进包括随机选择基准值、三数取中以及三向快速排序。对于包含大量重复元素的数据,三向分区能够把与基准值相等的元素集中处理,减少无效递归。

归并排序的时间复杂度则更稳定,通常为 O(nlog⁡n)O(n\log n),并且不依赖“这一次基准值选得好不好”。因此面对稳定性能要求、需要稳定排序或已经存在适合归并的数据结构时,归并排序可能更合适。

面试中怎样解释“为什么快”

可以按照“复杂度相同,常数不同”的结构回答:

  1. 两者平均或典型情况下都达到 O(nlog⁡n)O(n\log n),所以差异不来自数量级。
  2. 快速排序通常原地分区,归并排序通常需要辅助空间并进行额外的数据写入。
  3. 快速排序对连续数组的访问和就地处理,往往具有较好的缓存局部性。
  4. 快速排序的具体优势依赖基准选择、分区策略和数据分布,最坏情况下会退化。
  5. 归并排序具有稳定的复杂度和稳定排序特性,在链表、外部排序等场景中具有明显价值。

最终判断标准不是“哪个算法永远更快”,而是比较时间复杂度、额外空间、稳定性、数据分布以及具体实现的常数开销。

目录与阅读设置

记录一个想法

快速排序为什么常常比归并排序快

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通