Problem 1 (教材习题 7-4)

（快速排序的栈深度） 第6讲PPT第5页中的 QUICKSORT 算法包含了两个对其自身的递归调用。在调用 PARTITION 后， QUICKSORT 分别递归调用了左边的子数组和右边的子数组。 QUICKSORT 中的第二个递归调用并不是必须的。我们可以用一个循环控制结构来代替它。这一技术称为 尾递归 （tail recursion），好的编译器都提供这一功能。考虑下面这个版本的快速排序，它模拟了尾递归情况：

1. 证明：TAIL-RECURSIVE-QUICKSORT($A, 1, A.length$) 能正确地对数组 $A$ 进行排序。

编译器通常使用 栈 来存储递归执行过程中的相关信息，包括每一次递归调用的参数等。最新调用的信息存在栈的顶部，而第一次调用的信息存在栈的底部。当一个过程被调用时，其相关信息被 压入 栈中；当它结束时，其信息则被 弹出 。因为我们假设数组参数是用指针来表示的，所以每次过程调用只需要 $O(1)$ 的栈空间。 栈深度 是在一次计算中会用到的栈空间的最大值。

2. 请描述一种场景，使得针对一个包含 $n$ 个元素数组的 TAIL-RECURSIVE-QUICKSORT 的栈深度是 $\Theta(n)$ 。

3. 修改 TAIL-RECURSIVE-QUICKSORT 的代码，使其最坏情况下的栈深度是 $\Theta(\log n)$ ，并且能够保持 $O(n\log n)$ 的期望时间复杂度。

Solution

1. 用数学归纳法证明。

基础情况：若数组 $A$ 只有一个元素，即 $p = r$ ，算法第 1 行循环条件为否，数组保持不动，排序显然正确。

归纳假设：假设 TAIL-RECURSIVE-QUICKSORT 对于长度小于 $n$ 的数组都能够正确排序。

归纳步骤：算法第 3 行我们调用 PARTITION 来划分数组并得到主元下标 $q$ ，根据归纳假设，算法第 4 行的递归调用正确地将 $A[p..q-1]$ 排好了序。算法第 5 行将 $p$ 更新为 $q + 1$ ，然后重复上述步骤，对剩下的数组排序，根据归纳假设，每次循环的第 4 行总是能够正确地对一个子数组进行排序。循环直到不再剩下未排序的数组为止。因此， TAIL-RECURSIVE-QUICKSORT 能够对于长度为 $n$ 的数组正确排序。

归纳步骤中，关于算法第 1 到 5 行的 while 循环的作用，严谨的书写应当使用循环不变式来证明，这里因为问题比较简单，为了节省笔墨，仅作了简要描述。

综上所述，TAIL-RECURSIVE-QUICKSORT($A, 1, A.length$) 能正确地对数组 $A$ 进行排序。

2. 比如说输入已经排好序的时候，栈深度为 $\Theta(n)$ 。因为在输入排好序的情况下，每次划分后右数组的长度都为 $0$ ，左数组的长度为 $n - 1$ ，所以，在 $p < r$ 条件违反之前会有 $n - 1$ 次递归调用。而每次调用需要 $O(1)$ 的空间，所以栈深度为 $\Theta(n)$ 。

3. 算法的基本思路是，每次迭代递归地解决划分的两个子数组中较小的那个，较大的那个子数组留待下一次迭代重新进行划分。修改后的算法伪代码如下：

这样修改是为了能够尽可能的少在栈中储存数据，较小规模的递归调用意味着较少的栈空间消耗。

Problem 2 (教材习题 7-5)

（三数取中划分） 一种改进 RANDOMIZED-QUICKSORT 的方法是在划分时，要从子数组中更细致地选择作为主元的元素（而不是简单地随机选择）。常用的做法是三数取中法：从子数组中随机挑选出三个元素，取其中位数作为主元（见练习6问题5）。对于这个问题的分析，我们不妨假设数组 $A[1..n]$ 的元素是互异的且有 $n \ge 3$ 。我们用 $A&#x27;[1..n]$ 来表示已排好序的数组。用三数取中法选择主元 $x$ ，并定义 $p_i = Pr{x = A&#x27;[i]}$ 。

1. 对于 $i = 2, 3, \cdots, n-1$ ，请给出以 $n$ 和 $i$ 表示的 $p_i$ 的准确表达式（注意 $p_1 = p_n = 0$）。

2. 与平凡实现相比，在这种实现中，选择 $x = A&#x27;[\lfloor(n+1)/2\rfloor]$ （即 $A[1..n]$ 的中位数）的值作为主元的概率增加了多少？假设 $n \to \infty$ ，请给出两种实现下主元去到中位数的概率比值的极限值。

3. 如果我们定义一个“好”划分意味着主元选择 $x = A&#x27;[i]$ ，其中 $n / 3 \le i \le 2n/3$ 。与平凡实现相比，这种实现中得到一个好划分的概率增加了多少？（提示：用积分来近似累加和。）

4. 证明：对快速排序而言，三数取中法只影响其时间复杂度 $\Omega(n\log n)$ 的常数项因子。

Solution

1. $p_i$ 表示从 $n$ 个书中随机取 $3$ 个数，其中位数为 $A&#x27;[i]$ （数组 $A$ 中第 $i$ 小的元素）的概率。考虑古典概型，从 $n$ 个元素中随机取三个数，一共有 $C_n^3$ 种情况；从 $n$ 个元素中取三个数，使得 $A&#x27;[i]$ 为中位数，一共有 $(i-1)(n-i)$ 种情况——即先取一个比 $A&#x27;[i]$ 小的数字，有 $i - 1$ 种可能；再取一个比 $A&#x27;[i]$ 大的数字，有 $n - i$ 种可能。根据古典概型，有
   $p_i = \frac{(i-1)(n-i)}{C_n^3} = \frac{6(n-i)(i-1)}{n(n-1)(n-2)}$

2. 令 $i = \lfloor(n+1)/2\rfloor$ ，原本直接随机选择，$x = A&#x27;[i]$ 的概率为 $1 / n$ ，第 1 问中求出的三数取中法选择 $x = A&#x27;[i]$ 的概率为 $p_i$ ，概率增长了
   $\begin{aligned}$
   p_i - \frac{1}{n} &= \frac{(i-1)(n-i)}{C_n^3}\
   &= \frac{6(n-i)(i-1)}{n(n-1)(n-2)} - \frac{1}{n}\
   &= \frac{6(n-\lfloor(n+1)/2\rfloor)(\lfloor(n+1)/2\rfloor-1)}{n(n-1)(n-2)} - \frac{1}{n}
   \end{aligned}
   概率比值的极限为：
   $\lim_{n\to\infty}\frac{\frac{6(n-\lfloor(n+1)/2\rfloor)(\lfloor(n+1)/2\rfloor-1)}{n(n-1)(n-2)}}{\frac{1}{n}} = \frac{3}{2}$

3. 因为取整对于求和影响不大，我们不妨假设 $n$ 是 $3$ 的倍数，我们可以通过积分来近似求和，得到“好”划分的概率为
   $\begin{aligned}$
   \sum_{i = n/3}^{2n/3} p_i
   &= \frac{6(n-i)(i-1)}{n(n-1)(n-2)}\
   &\approx \int_{n/3}^{2n/3}\frac{6(n-x)(x-1)}{n(n-1)(n-2)}\text{d}x\
   &=\frac{(\frac{13}{27}n-1)n}{(n-1)(n-2)}\
   \end{aligned}
   而原来得到一个好划分的概率为 $(2n/3 - n/3)/(n) = 1/3$ ，为了比较方便，我们可以考虑 $n$ 特别大的情况，对上述积分结果求极限，得到三数取中法在极限情况下得出“好”划分的概率为 $13/27$ 。 $13 / 27 > 1/3$ ，因此三数取中法增加了取到“好”划分的概率，具体地，在极限情况下增加了 $13/27 - 1/3 = 4/27$。

4. 即使说我们每次都能够极其幸运地取到整个待划分数组的中位数作为划分的主元，该递归算法的复杂度依旧是 $\Omega(n\log n)$ ，因为递归树至少 $\log n$ 层，每层的总代价都为 $n$ 。因此该算法只是增加了取到“好”划分的概率，但是并不会让算法突破它的最好情况运行时间的下界。

Problem 3 (教材习题 7-6)

（对区间的模糊排序） 考虑这样的一种排序问题：我们无法准确知道待排序的数字是什么。但对于每一个数，我们知道它属于实数轴上的某个区间。也就是说，我们得到了 $n$ 个形如 $[a_i, b_i]$ 的闭区间，其中 $a_i \le b_i$ 。我们的目标是实现这些区间的 模糊排序 ，即对 $j = 1, 2, \cdots, n$ ，生成一个区间的排列 $\langle i_1, i_2, \cdots, i_n\rangle$ ，且存在 $c_j \in [a_{i_j}, b_{i_j}]$ ，满足 $c_1\le c_2\le \cdots \le c_n$ 。

1. 为 $n$ 个区间的模糊排序设计一个随机算法。你的算法应该具有算法的一般结构，它可以对左端点（即 $a_i$ 的值）进行快速排序，同时它也能利用区间的重叠性质来改善时间性能。（当区间重叠越来越多的时候，区间的模糊排序问题会变得越来越容易。你的算法应能充分利用这一重叠性质。）

2. 证明：在一般情况下，你的算法的期望运行时间为 $\Theta(n \log n)$ 。但是，当所有的区间都有重叠的时候，算法的期望运行时间为 $\Theta(n)$ （也就是说，存在一个值 $x$ ，对所有的 $i$ ，都有 $x \in [a_i, b_i]$ 。）你的算法不必显式地检查这种情况，而是随着重叠情况的增加，算法能自然地提高。

Solution

1. 这里区间排序和数字排序的整体逻辑是一样的，只是区间之间的大小比较规则和数字有所不同罢了。

   根据题设定义，我们可以将区间无重叠的左右关系视为大小关系（左侧的区间小于右侧的区间），将区间的重叠关系视为“相等”关系。由于这里存在区间“相等”的情况，我们可以借鉴作业6-1问题2的做法，和“主元”“相等”的元素就没必要参与下一次递归了。

2. 一般情况下，上述算法的复杂度和普通的快速排序一样，都是 $O(n\log n)$ 。当输入序列的所有区间都有重叠的时候，FUZZY-PARTITION($A, 1, n$) 会返回 $(1, n)$ ，因为所有元素和主元都是“相等”的 ，从而算法第 6 到 7 行的两次递归调用都会在其第 4 行的检查处直接返回，运行时间为 $\Theta(1)$ 。因此，整个算法的运行时间就是 FUZZY-PARTITION的运行时间，不难得出为 $\Theta(n)$ 。

   不难发现，重叠的区间越多，递归调用时的子问题规模就越小，算法的运行时间也会随之降低。