题目重点：给出期望比较次数递推，解释随机化假设、重复值与递归栈深度。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 分析n个不同key，pivot每次均匀选当前子数组元素，划分本次比较n−1次。
- 重复key要用三路等值分区另分析；不把平均复杂度当单次最坏保证。
解题路线
- 一次partition后pivot定位置，左右子问题规模分别k和n−1−k。本次线性成本并不自动证明总n log n，必须分析递归划分是否长期平衡。
- 均匀pivot的排名k均匀0至n−1，因此期望C(n)=n−1+(1/n)Σ[C(k)+C(n−1−k)]=n−1+(2/n)ΣC(k)，C(0)=C(1)=0。
- 递推解为2(n+1)H_n−4n，调和数H_n=Θ(log n)，故期望Θ(n log n)。也可按一对元素在递归中被比较的概率2/(距离+1)求和，说明平均来自pivot随机排名。
- 若固定选首项且输入升序，每次规模0和n−1，T(n)=T(n−1)+Θ(n)，总Θ(n²)。随机选择使这种坏划分概率降低，但不消除单次最坏可能。
- 大量相等元素若二路partition把等值都偏向一侧，也会退化；三路分为小于、等于、大于，只递归两边，等值区域一次完成。该情形不满足不同key递推的原假设。
- 普通递归栈期望O(log n)、最坏O(n)。优先递归较小侧并循环处理较大侧可限制栈深O(log n)，但不把坏输入总时间变为n log n。示例验证所有短排列的比较平均与递推一致。
手动走一遍
n=3时pivot排名0/1/2概率各1/3，平均比较2+(2/3)·C(2)=8/3；并非每次正好n log n。固定首pivot在升序n项会累计(n−1)+(n−2)+…+1。
规模与取舍
不同key随机pivot期望O(n log n)，最坏O(n²)；原地划分额外常量，递归栈依策略期望/最坏不同。随机数和key比较成本另计。
易错点与追问
容易失分的边界
- “每层n、一共log n层”未说明为什么平衡。
- 平均界说成最坏界。
- 重复值直接套不同key证明。
继续深挖
- 三路划分怎样改变等值处理？
- 如何限制递归栈而保留坏时间？
- introsort何时切换策略？
