（三数取中划分）一种改进RANDOMIZED-QUICKSORT的方法是在划分时，要从子数组中更细致的选择作为主元的元素（而不是简单的随机选择）。常用的做法是三数取中法：从子数组中随机选出三个元素，取其中位数作为主元。对于这个问题的分析，我们不妨假设数组A[1...n]的元素是互异的且有
。我们用A'[1,...,n]来表示已排好序的数组。用三数取中法选择主元x，并定义pi=Pr{x=A'[i]}。
a.对于i=2,3,...,n-1，请给出以n和i表示的pi的准确表达式（注意p1=pn=0）。
b.与平凡实现相比，在这种实现中，选择
(即A[1,...,n]的中位数)的值作为主元的概率增加了多少？假设
，请给出这一概率的极限值。
(即A[1,...,n]的中位数)的值作为主元的概率增加了多少？假设 c.如果我们定义一个“好”划分意味着主元选择x=A'[i]，其中
。与平凡实现相比，这种实现中得到一个号划分的概率增加了多少？（提示：用积分来近似累加和）。
d.证明：对快速排序而言，三数取中法只影响其时间复杂度)
的常数项因子。
