使用快速排序对n个元素列表排序的最小递归调用次数问题

核心规则澄清 #

你对这个问题存疑非常合理，题目本身没有统一两个关键统计标准，不同标准下答案差异很大：

• 统计范围差异：是否计入最外层第一次手动触发的快排函数调用，两种统计结果仅差常数1，核心规律一致。
• 实现逻辑差异：快排有两种常见实现：一种是无判断的原始写法，partition后直接对左右区间执行递归调用，哪怕子数组长度为0或1也会产生一次调用；另一种是通用优化写法，仅对子数组长度≥2的区间发起递归，长度0、1的区间直接返回，不产生新调用。
• “最小递归调用次数”的定义很明确：快速排序的调用次数和每次pivot（基准值）的选择直接相关，最小次数就是pivot选择策略最优时，全程产生的函数调用总次数。

目前国内算法教材、笔试面试中考察该问题时，默认采用优化版快排实现+统计包含初始调用在内的所有函数调用的规则，以下结论均基于该通用规则。

结论推导 #

首先纠正一个常见误区：多数人误以为每次pivot将数组拆分为两个等长段时调用次数最少，实际恰好相反。要最小化总调用次数，核心是每次拆分后尽可能少产生需要递归处理的长区间。最优pivot选择策略为：每次选点让其中一侧子数组长度为1（无需递归），另一侧子数组尽可能取到“单次递归即可处理完成、无后续调用”的最大长度。

按该策略推导的结果为：

• n=1时，仅需1次初始调用，无后续递归，总次数1
• n为2、3时，单次调用即可完成处理，拆分后子数组长度均≤1，无需额外递归，总次数1
• n为4~7时，最少需要2次调用
• n为8~15时，最少需要3次
• 通用规律：当数组长度n落在[2^k, 2^(k+1)-1]区间时，最小递归调用次数为k（n=1为边界情况，单独记为1次即可）。

注意：网上大量相关回答给出的结果⌈log₂(n+1)⌉实际是最小递归深度（即递归过程中函数调用栈的最大层数），并非总调用次数。该深度出现在每次pivot都将数组拆分为两个等长子区间的场景，不少出题人、初学者会混淆递归深度和递归调用次数的概念，如果是应试场景可以优先记这个结论。

内容的提问来源于stack exchange，提问作者Snehashish Das