【思考题】
7-1 Hoare 划分的正确性
a) 说明 HOARE-PARTITION 算法在数组 A = <13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21> 上的运行过程，
并说明在第 4~11 行中 while 循环的每一轮迭代后，数组中各元素的之和辅助值的情况。
p=1, r=12
[i=0] 13 19 9 5 12 8 7 4 11 2 6 21 [j=13]
6 [i=1] 19 9 5 12 8 7 4 11 2 [j=11] 13 21
6 2 [i=2] 9 5 12 8 7 4 11 [j=10] 19 13 21
i=10, j=9
return j = 9
b) 下标i和j满足这样的特点，即我们从不会访问数组A的、在子数组A[p..r]之外的元素。
第一次迭代后，若i与j相同，则只有 A[i] = A[j] = x = A[p] 一种情况，直接返回j。
若i与j不相同，则交换A[i] A[j]，而在之后某次导致i>=j的迭代中，i至少会被之前的值为A[i]的元素拦截下来，同理，j也会被过去的A[j]拦截而不会越界。之后迭代结束返回j。
因此，不会访问到子数组之外的元素。
c) 当过程 HOARE-PARTITION 结束时，他返回的j值满足p<=j<r。
注意到只有 i>=j 时过程结束，每次迭代，i至少+1，j至少-1。
而第一次迭代就结束过程，只有当A[i] = A[j] = x = A[p]时才会出现，此时j=p。
若第一次迭代后过程没有结束，则j最大为r-1，即j<r。
其余情况，j可能为[p,r)中的任意数。
综上，p<=j<r。
d) 当过程 HOARE-PARTITON 结束时，A[p..j] 中的每个元素都小于或等于A[j+1..r] 中的每一个元素。
使用循环不变式。证明A[j+1..r]中的每个元素都小于或等于x。
初始化：第一次迭代前，j=r+1，显然，在第一次循环之前循环不变式成立。
保持：假设在第i次循环迭代之前，A[j+1..r] 中的每个元素都大于或等于x。迭代后，由于A[i]>=x，A[j]<=x，交换后A[j]>=x。为下一次迭代保持了性质。
终止：在结束时，A[j]是一个<=x的元素，但是A[j+1..r]中的每个元素都大于或等于x。因此不变式成立。
同理可证：A[p..i-1]中每一个元素都小于或等于x。而i>=j，因此，A[p..i-1]<=x<=A[j+1..r]即A[p..j]<=x<=A[j+1..r]。
e) 利用 HOARE-PARTITION，重写 QUICKSORT 过程。
int hoarePartition(int A[],int p,int r) {
int x = A[p];
int i = p - 1;
int j = r + 1;
while (true) {
do {
j--;
}while (A[j]>x);
do {
i++;
}while (A[i]<x);
if (i<j) {
swap(A[i],A[j]);
}
else return j;
}
}
void hoareSort(int A[],int p,int r) {
if (p < r) {
int q = hoarePartition(A,p,r);
hoareSort(A,p,q);
hoareSort(A,q+1,r);
}
}7-2 对快速排序算法的另一种分析
a) 证明：给定一个大小为n的数组，任何特定元素被选作主元的概率为1/n。利用这个结论来定义指示器随机变量 Xi = I{第i个最小的元素被选作主元}。E[Xi]是多少？
b) 设T(n)是一个表示快速排序在一个大小为n的数组上的运行时间的随机变量。证明：
c) 证明(b)中的公式可以改写为
d) 证明：
e) 利用(d)式中给出的界，证明式(c)中的递归式有解E[T(n)]=⊙(nlgn)。
7-3 Stooge 排序
void stoogeSort(int A[],int i,int j) {
if (A[i]>A[j]) swap(A[i],A[j]);
if (i+1>=j) return;
int k = (j-i+1)/3;
stoogeSort(A,i,j-k);
stoogeSort(A,i+k,j);
stoogeSort(A,i,j-k);
}a) 证明：如果n=length[A]，那么STOOGE-SORT(A,1,length[A])能正确地对输入数组A[1..n]进行排序。
循环不变式：在STOOGE-SROT(A,p,r)调用结束后，A[p..r]是已排序的。
初始化：当i+1>=j时，递归返回。i=j 时，A[i..i]有序；i+1=j时，由于上面的交换，A[i..j]有序。
保持：假设在某次STOOGE-SORT调用的中，内部的STOOGE-SORT都满足循环不变式。
将数组划分为A|B|C三部分，第一次递归，将AB内元素排序，第二次递归，将BC内元素排序，此时数组中最大的元素在C区域。
第三次递归，将AB内元素排序，此时A<=B<=C，循环不变式得到了保持。
终止：STOOGE-SORT(A,1,length[A])调用后，A数组内元素是已排序的。
b) 给出一个表达式 STOOGE-SORT 最坏情况运行时间的递归式，以及关于最坏情况运行时间的一个紧确的渐进(⊙记号)界。
T(n)=3T(2n/3)+Θ(1)
由主定理的情形一：
c) 比较 STOOGE-SORT 与插入排序、合并排序、堆排序和快速排序的最坏情况运行时间。
插入排序、快速排序：Θ(n^2)
堆排序、合并排序：Θ(nlogn)
STOOGE-SORT：Θ(n^2.709511291351454776976190262174)
7-4 快速排序中的堆栈深度
7-5 三数取中划分
a) 对i=2,3,...,n-1，给出pi的以n和i表示的准确表达式。
b) 与一般实现比较，这种实现中取A[1..n]的中值x=A'[(n+1)/2]的可能性增加了多少？假设n->OO，请给出这两个概率比值的极限。
c) 如果定义一个好的划分是选择了x=A'[i]，其中n/3<=i<=2n/3，则与一般实现相比，此时得到了一个好的划分的可能性增加了多少？
d) 论证对快速排序而言，三数取中方法仅影响其运行时间Ω(nlogn)中的常数因子。
7-6 对区间的模糊排序
a) 为n个区间的模糊排序设计一个算法。
b) 证明：在一般情况下，你的算法的期望运行时间为Θ(nlogn)，但当所有区间都重叠时，期望的运行时间为Θ(n)