Question

8.1 排序算法时间的下界

8.1-1
<span style="line-height: 20px; ">n-1，因为一个有序数组的排序中最少会进行 n-1 次比较</span>
8.1-2
数学题目不要看我
8.1-3
幸好有答案，不然题目的意思都看不懂。先解释一下题目的意思，高手跳过。
对于一个组包含 n 个元素的数据，可以有 n!种不同的排列，也就是有 n!种不同的输入。
对于一个排序算法，可以用一个决策树来表示。
对于任意一种输入排列，从树顶出发，根据该内结点的提示作对应的比较和调整，并决定进入其左子树还是右子树。当这个排列成为一个有序序列时到达叶子结点。这个叶结点就是这个输入排列对应的叶结点。从根结点到叶结点的长度就是这个排列的比较次数。
具有线性时间的输入是指 n!种输入排列中满足以下条件的排列：排列的运行时间小于或等于 O(n)
假设对于一组包含 n 个元素的数据，有 n!种不同的输入排列，其中具有线性时间的输入排列有 m 种，求 k = m/(n!)
若 k<=1/2，那么所证明的命题成立。
后面一问是指 k 和 1/n、1/(2^n) 的比较
证明：
这 m 种输入排列分别对应决策树中的 m 个叶结点。一棵高度为 h 的树最多有 2^h 个叶结点。
2^h >= m =====> h >= lg(m)
若要一棵决策树包含 m 个叶结点，这棵决策树的高度最少为 lg(m)
根据《算法导论》P98 中定理 8.1 的公式，h>=O(nlgn)
只需要证明 lg(m) <= O(nlgn)，那么 k 就是可以取到的值。
分别令 k 等于 1/2、1/n、1/(2^n),代入 m = k * (n!) 得：
计算结果略，这几个值都不满足
8.1-4
不能简单地将子序列的下界合起来，这样做不准确。因为有可能存在一种比“独立解决各个子序列的排序”更快的算法。
这种计算比较次数的一般思路是：
(1) 统计有多少种不同的输入排列
(2) 每一种输入排列对应决策树的一个叶子结点。
(3) 根据叶结点的数量与树的高度的关系，计算决策树的高度
(4) 从树根到叶结点的长度就是这个叶结点对应的输入排列的比较次数
对于这道题，可以这样计算：
(1) 每个子序列有 k 个元素，因此有 k!种不同的输入排列。
共有 n/k 个子序列，因此共有(k!)^(n/k) 种输入排列
(2) 决策树至少有(k!)^(n/k) 个叶子
(3) 一棵高度为 h 的决策树，最多有 2^h 个叶子结点
2^h >= (k!)^(n/k)   =====>   h >= (n/2)lg(k/2)
(4) 对于任意一树决策树，至少有一条叶子路径长度超过(n/2)lg(k/2)，因此比较次数下界是 O(nlgk)

8.2 计数排序

8.2-1 因为假设待排序数据的范围中[0,k]，所以 B 被初始化为-1
  A = {6 0 2 0 1 3 4 6 1 3 2}
==> C = {2 2 2 2 1 0 2}
==> C = {2 4 6 8 9 9 11}
==> B = {-1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1}
  C = {2 4 5 8 9 9 11}
==> B = {-1 -1 -1 -1 -1 2 -1 3 -1 0 -1 -1}
  C = {2 4 5 7 9 9 11}
==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 -1}
  C = {2 3 5 7 9 9 11}
==> B = {-1 -1 -1 1 -1 2 -1 3 -1 -1 6}
  C = {2 3 5 7 9 9 10}
==> B = {-1 -1 -1 1 -1 2 -1 3 4 -1 6}
  C = {2 3 5 7 8 9 10}
==> B = {-1 -1 -1 1 -1 2 3 3 4 -1 6}
  C = {2 3 5 6 8 9 10}
==> B = {-1 -1 1 1 -1 2 3 3 4 -1 6}
  C = {2 2 5 6 8 9 10}
==> B = {-1 0 1 1 -1 2 3 3 4 -1 6}
     C = {1 2 5 6 8 9 10}
==> B = {-1 0 1 1 2 2 3 3 4 -1 6}
     C = {1 2 4 6 8 9 10}
==> B = {0 0 1 1 2 2 3 3 4 -1 6}
     C = {0 2 4 6 8 9 10}
==> B = {0 0 1 1 2 2 3 3 4 6 6}
     C = {0 2 4 6 8 9 9}
8.2-2
辅助数组 C[j]记录的是小于或等于 i 的元素的个数。若几个元素的大小相等，则把这些元素依次从后往前填入排序数组中。因为处理元素的顺序是从后往前的(L9)，所以晚出现的元素会填到后面。因此是稳定排序
8.2-3
不稳定
8.2-4
COUNTING-SORT(A, B, k) 中步骤 L1-L4 求出 C，ans(a, b) = C[b] - C[a-1], C[-1]=0

8.3 基数排序

8.3-1

  A = {COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX}
==> A = {SEA, TEA, MOB, TAB, DOG, RUG, DIG, BIG, BAR, EAR, TAR, COW, ROW, NOW, BOX, FOX}
==> A = {TAB, BAR, EAR, TAR, SEA, TEA, DIG, BIG, MOB, DOG, COW, ROW, NOW, BOX, FOX, RUB}
==> A = {BAR, BIG, BOX, COW, DIG, DOG, EAR, FOX, MOB, NOW, ROW, TAB, TAR, TEA, SEA, RUB}

8.3-2
稳定排序有：插入排序，合并排序

方法：为每一个元素加入一个最初位置的属性，但两个元素的 value 一样大时，比较 position，这样不会有相同的两个元素

额外空间：O(4n)

8.3-3
(1) 当 d=1 时，元素只有一位，对这一位做排序就相当于对整个数组做排序了。
(2) 证明当 1 到 d-1 位排序是正确的时，对 d 位的排序也是正确的。
(3) 对于数组中的任意两个数 a 和 b，假设它们的第 d 位分别是 ad 和 bd
若 ad<bd，则 a 会排到 b 的前面
若 ad>bd，则 a 会排到 b 的后面
若 ad=bd，则 a 和 b 的相对位置不变，因为是稳定排序，这一点可以保证。

8.3-4

把整数转换为 n 进制再排序，见 算法导论 8.3-4

8.3-5

最坏情况下需要 d 遍

8.4 桶排序

8.4-1
  A = ｛0.79， 0.13， 0.16， 0.64， 0.39， 0.20， 0.89， 0.53， 0.71， 0.42｝
==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.79， 0.71， 0.89｝
==> A = ｛0.13， 0.16， 0.20， 0.39， 0.42， 0.53， 0.64， 0.71， 0.79， 0.89｝
8.4-2
最坏情况是 O(n^2)
修改：使用最坏情况下时间为 O(nlgn) 的算法来处理桶的插入操作
8.4-3
E(X^2)=1/4 * 0 + 1/2 * 1 + 1/4 * 4 = 3/2
E^2(X)=[1/4 * 0 + 1/2 * 1 + 1/4 * 2]^2 = 1^2 = 1
8.4-4
假设分为 n 个桶
BUCKET-SORT(A)
1  n <- length[A]
2  for i <- 1 to n
3  do insert A[i] to list B[n*(A[i].x^2 + A[i].y^2)]
4  for i <- 0 to n-1
5    do sort list B[i] with insertion sort
6  concatenate the lists B[0], B[1], ……,B[n-1] together in order
8.4-5

不会，网上找了份答案，不懂
X 合适分布 P，不必然是均匀分布，且不知局限。但 P(x) 值属于[0,1]，且对于 X 严格单调递增，排序 P(x) 即排序 X。将 P(x) 均匀分为 n 个项目组，因为 X 随机拔取，所以落入每个局限的概率雷同。
若是(i-1)/n <= p(xi) < i/n，则将它放入第 i 个桶中。
http://www.mysjtu.com/page/M0/S696/696126.html