14 快速排序
双指针分区、枢轴、退化与短侧优先
第 01 题 问题 1
快速排序重要工作在递归前还是递归后？
参考答案
递归前的划分。
解析
划分固定枢轴并把数据分到两侧，之后递归排序子区间。
第 02 题 问题 2
有重复键时划分两侧应理解为严格小于、大于吗？
参考答案
一般不能；本实现左侧 <= pivot，右侧 >= pivot。
解析
等于枢轴的记录可能存在两侧，具体约束由划分实现决定。
第 03 题 问题 3
闭区间递归的正确终止条件是什么？
参考答案
low >= high。
解析
涵盖空区间与单项，不应让空区间继续索引访问。
第 04 题 问题 4
为什么递归区间必须排除枢轴位置 p？
参考答案
枢轴已经在最终位置；排除它使问题规模严格减小。
解析
区间应为 [low,p−1] 与 [p+1,high]；否则可能重复处理或无限递归。
第 05 题 问题 5
三数取中对 [15,21,8] 应选择哪个值？
参考答案
15。
解析
取三项排序后的中间值，不是平均数 (15+21+8)/3。
第 06 题 问题 6
末尾枢轴处理升序输入为什么容易退化？
参考答案
枢轴总是最大值，划分反复得到 n−1 与 0。
解析
普通递归版时间 O(n²)，栈最坏 O(n)。
第 07 题 问题 7
三数取中是否保证任何输入都 O(n log n)？
参考答案
不保证。
解析
能改善常见输入，但仍存在不均衡划分，不能把启发式当作最坏保证。
第 08 题 问题 8
双指针遇到两个都等于 pivot 的项时，交换后为何要移动指针？
参考答案
保证循环取得进展，避免重复比较同一对位置。
解析
两个扫描条件都不成立时，没有主动前进可能死循环。
第 09 题 问题 9
Python a[-1] 合法，是否可以省略左边界检查？
参考答案
不能。
解析
负下标会读取末项，不会自动报越界；算法需明确检查 i、j 的范围。
第 10 题 问题 10
怎样把迭代快排的待处理栈控制在对数级？
参考答案
把较长区间压栈，立即处理较短区间。
解析
立即处理的短侧至多约半长；这是空间控制，不会消除 O(n²) 最坏时间。
第 11 题 问题 11
本教材原地快排是稳定排序吗？
参考答案
不是。
解析
[2A,2B,1X] 最后放置末尾枢轴 1X 可得到 [1X,2B,2A]。
第 12 题 问题 12
cutoff=8 的意义是什么？能当作通用最优值吗？
参考答案
长度不超过 8 的区间改用插入排序；不能视为通用最优。
解析
小区间常数开销、比较成本、语言与硬件会影响阈值。