Question

8-1 比较排序的平均情况下界

a)n 个不同的元素对应 n!个不同的输入，因此只有这 n!个输入所对应的叶结点是有概率的，其余概率均为 0。
由于这 n!种输入的出现是等概率的，每一种的都是 1/n1，因此其对应的叶结点的概率也是 1/n!
b) 设 T(n) 是一个叶子结点 n 的在决策树 T 上的深度，RT(n)、LT(n) 分别表示 n 在 T 的右、左子树上的深度。
那么 T(n)=RT(n)+1 或 T(n)=LT(n)+1
因此 D(T)=D(RT)+D(LT)+k
c) 后面这几题，以我有限的智商和数学能力理解不了，也看不懂网上的答案，不写了

8-2 以线性时间原地转换排序

a) 计数排序
b) 快速排序
c) 稳定排序
d) 基数排序要求所使用的排序方法是满足的（条件 2），如果要在 O(bn) 时间内完成，所使用算法的时间应该是 O(n)（条件 1），所以只有 a 可以
e) 不稳定
COUNTING-SORT(A, k)
 1  for i <- 0 to k
 2    do C[i] <- 0
 3  for j <-1 to length[A]
 4    C[A[j]] <- C[A[j]] + 1
 5  cnt <- 1
 6  for i <- 1 to k
 7    while C[i] > 0
 8      A[cnt] <- i
 9      C[i] <- C[j] - 1
10      cnt <- cnt + 1

8-3 排序不同长的数据项

见 算法导论-8-3-排序不同长度的数据项

a) 先用计数排序算法法按数字位数排序 O(n)，再用基数排序的方法分别对每个桶中的元素排序 O(n)
b) 递归使用计数排序，先依据第一个字母进行排序，首字相同的放在同一组，再对每一组分别使用计数排序的方法比较第二个字母
见到有人用字典树，也是可以的

8-4 水壶

a) 最原始的比较方法，所有的红水壶与所有的蓝水壶依次比较
c) 算法类似于快排，由于不是同种颜色的水壶之间比较，所以采用交叉比较
step1：从红色水壶中随机选择一个
step2：以红色水壶为主元对蓝色水壶进行划分
step3：划分的结果是两个数组，并得到与红色水壶相同大小的蓝色水壶
step4：以这个蓝色水壶为主元，对红色水壶进行划分
step5：用 step1 到 step4 的过程不断迭代

8-5 平均排序

见 算法导论 6.5-8 堆排序-K 路合并

a)1 排序是完全排序
b)1，3，2，4，5，7，6，8，9，10
c) 分工展开化简即可
d)
step1：分别把 1, 1+k, 1+2k, 1+3k,……;2, 2+k, 2+2k, 2+3k,……；……当作是单独的集合
step2：对每个集合进行排序时间为 O(nlg(n/k))
e)
step1：同 d)step1
step2：用堆排序进行 k 路合并

 

8-6 合并已排序列表的下界

a)2n 个数，随机选 n 个数，可选的方法有 C(2n,n) 种
b)2^h >= C(2n,n)
=====>   h >= lg((2n)!) - 2lg(n!)
=====>   h >= 2nlg2n - 2nlgn
=====>   h >= 2nlg2
只能推到这了，最后怎么算，还希望高手指点
c)d) 看上去很显然的事情，不知道怎么证