算法导论8.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

8.2-1

第一次循环结束后，得到数组$C=\langle2,2,2,2,1,0,2\rangle$.

第二次循环结束后，得到数组$C=\langle2,4,6,8,9,9,11\rangle$.

那么第三次循环，依次得到：

$\begin{array}{ll}
B&C\
\langle\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2}\rangle & \langle2,4,6,8,9,9,11\rangle\
\langle\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},2,\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2}\rangle & \langle2,4,5,8,9,9,11\rangle\
\langle\phantom{2},\phantom{2},\phantom{2},\phantom{2},\phantom{2},2,\phantom{2},3,\phantom{2},\phantom{2},\phantom{2}\rangle & \langle2,4,5,7,9,9,11\rangle\
\langle\phantom{2},\phantom{2},\phantom{2},1,\phantom{2},2,\phantom{2},3,\phantom{2},\phantom{2},\phantom{2}\rangle & \langle2,3,5,7,9,9,11\rangle\
\langle\phantom{2},\phantom{2},\phantom{2},1,\phantom{2},2,\phantom{2},3,\phantom{2},\phantom{2},6\rangle & \langle2,3,5,7,9,9,10\rangle\
\langle\phantom{2},\phantom{2},\phantom{2},1,\phantom{2},2,\phantom{2},3,4,\phantom{2},6\rangle & \langle2,3,5,7,8,9,10\rangle\
\langle\phantom{2},\phantom{2},\phantom{2},1,\phantom{2},2,3,3,4,\phantom{2},6\rangle & \langle2,3,5,6,8,9,10\rangle\
\langle\phantom{2},\phantom{2},1,1,\phantom{2},2,3,3,4,\phantom{2},6\rangle & \langle2,2,5,6,8,9,10\rangle\
\langle\phantom{2},0,1,1,\phantom{2},2,3,3,4,\phantom{2},6\rangle & \langle1,2,5,6,8,9,10\rangle\
\langle\phantom{2},0,1,1,2,2,3,3,4,\phantom{2},6\rangle & \langle1,2,4,6,8,9,10\rangle\
\langle0,0,1,1,2,2,3,3,4,\phantom{2},6\rangle & \langle0,2,4,6,8,9,10\rangle\
\langle0,0,1,1,2,2,3,3,4,6,6\rangle & \langle0,2,4,6,8,9,9\rangle\
\end{array}$

8.2-2

考虑两个下标$i,j$满足$A[i]=A[j]=x,i< j$。第11行的逆序for循环将会使得$A[j]$先被访问，$A[i]$后被访问。当访问到$A[j]$时，数$A[j]$被放置到了数组$B$中的位置$C[x]$，接下来$C[x]$将会自减$1$。由于这个for循环中，$C$数组中的所有值只会递减，不会递增，因此当访问到$A[i]$时，此时的$C’[x]<C[x]$，即彼时访问$A[j]$前的$C[x]$。因此，$A[i]$将会放置到位置$C’[x]$中，保持了相对顺序。因此，这种实现下的计数排序是稳定的。

8.2-3

将循环正序，并不会影响排序的正确性。只要键相同，先后放置顺序并不重要，不同元素间的顺序将仍然保持。排序程序转换成不稳定的原因是对于两个下标$i,j$满足$A[i]=A[j]=x,i< j$，由于$i$先被遍历，$j$后被遍历，但是第11行的for循环下，$C$数组仍然是递减的，这将导致排序后，$A[i]$会被放置在$A[j]$的后面，因此仍然是不稳定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
COUNTING-SORT'(A, n, k)
  let B[1 : n] and C[0 : k] be new arrays
    for i = 0 to k
      C[i] = 0
  for j = 1 to n
    C[A[j]] = C[A[j]] + 1
  // C[i] now contains the number of elements equal to i.
  s = 0
  for i = 0 to k
    c = C[i]
    C[i] = s
    s += c
  // Copy A to B, starting from the end of A.
  for j = 1 to n
    C[A[j]] = C[A[j]] + 1 // to handle duplicate values
    B[C[A[j]]] = A[j]
  return B

8.2-4

初始化：一开始值为$n$的循环迭代前，$C[i]$表示数组$A$中有多少个数小于等于$i$，也就是最后一个$i$所放置的位置，循环不变量成立。

保持：在值为$i$的循环开始前，$C[A[i]]$代表着当前数$C[A[i]]$中应该放置的位置。第12行的代码将$A[i]$放置到正确的位置，第13行将$C[A[i]]$自减$1$，如果存在下一个$A[j]=A[i]=x,j< i$，那么它确实应该放置在$C[A[i]]-1$处，因为两个数相同，应该放在一起；如果不存在，那么$C[A[i]]$的值永远不会被访问到，可以忽略。因此，值为$i$的循环完成后，数组$C$的含义仍然保持，循环不变量成立。

终止，循环完成后，数组$C$中所有值都将被忽略，数组$B$是个有序的数组，循环正确终止。

8.2-5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 没有卫星数据，意味着不需要考虑排序的稳定性，直接赋值即可。
COUNTING-SORT''(A, n, k)
  let C[0 : k] be new array
    for i = 0 to k
      C[i] = 0
  for j = 1 to n
    C[A[j]] = C[A[j]] + 1
  // C[i] now contains the number of elements equal to i.
  p = 0
  for i = 0 to k
    for j = 1 to C[i]
      p += 1
      A[p] = i
  return A

8.2-6

可以发现，算法ANSWER-QUERY的第10行中，每次循环都是$O(1)$常数级别的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//数组Q表示询问列表，Q[i].a和Q[i].b表示题中的a和b。 
ANSWER-QUERY(A, n, k, Q, q)
  let B[1 : q], C[0 : k] be new array
    for i = 0 to k
      C[i] = 0
  for j = 1 to n
    C[A[j]] = C[A[j]] + 1
  // C[i] now contains the number of elements equal to i.
  for i = 1 to k
    C[i] = C[i] + C[i – 1]
  // C[i] now contains the number of elements less than or equal to i.
  for i = 1 to q
    s = C[Q[i].b]
    // 减去区间[0, a)中的所有数，为了避免越界，需要进行判断。
    if Q[i].a > 0
      s = s - C[Q[i].a - 1]
    B[i] = s
  return B

8.2-7

基本思想是：通过对每个浮点数乘以$10^d$转换成整数，再统计到下标中，然后排序完成后再转换成浮点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
COUNTING-SORT-FLOAT(A, n, k, d)
  // 假设POW(10, d)是一个常数，能以O(1)的时间被计算出。
  K = k * POW(10, d)
  let B[1 : n], C[0 : K] be new array
    for i = 0 to K
      C[i] = 0
  for j = 1 to n
    t = A[j] * POW(10, d)
    C[t] = C[t] + 1
  // C[i] now contains the number of elements equal to i.
  for i = 1 to K
    C[i] = C[i] + C[i – 1]
  // C[i] now contains the number of elements less than or equal to i.
  for j = n downto 1
    t = A[j] * POW(10, d)
    B[C[t]] = A[j]
    C[t] = C[t] – 1
  return B