算法导论8.2 Exercises 答案

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]\)的后面，因此仍然是不稳定的。

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

// 没有卫星数据，意味着不需要考虑排序的稳定性，直接赋值即可。
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)\)常数级别的。

//数组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\)转换成整数，再统计到下标中，然后排序完成后再转换成浮点数。

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