算法导论7.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 880 阅读时长 ≈ 1 分钟

7.1-1

\(\begin{aligned} &\langle13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11\rangle\\ &\langle[9, 5, 8, 7, 4, 2, 6, \underline{11}, 21, 13, 19, 12]\rangle\\ &\langle[5, 4, 2, \underline{6}, 9, 8, 7], 11, 21, 13, 19, 12\rangle\\ &\langle[\underline{2}, 4, 5], 6, 9, 8, 7, 11, 21, 13, 19, 12\rangle\\ &\langle2, [4, \underline{5}], 6, 9, 8, 7, 11, 21, 13, 19, 12\rangle\\ &\langle2, 4, 5, 6, [\underline{7}, 8, 9], 11, 21, 13, 19, 12\rangle\\ &\langle2, 4, 5, 6, 7, [8, \underline{9}], 11, 21, 13, 19, 12\rangle\\ &\langle2, 4, 5, 6, 7, 8, 9, 11, [\underline{12}, 13, 19, 21]\rangle\\ &\langle2, 4, 5, 6, 7, 8, 9, 11, 12, [13, 19, \underline{21}]\rangle\\ &\langle2, 4, 5, 6, 7, 8, 9, 11, 12, [13, \underline{19}], 21\rangle\\ &\langle2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 19, 21\rangle\\ \end{aligned}\)

7.1-2

将会返回\(r\)，因为所有元素都小于等于同一个值，它们都被划分到左半部分。

考虑使用HOARE-PARTITION可以解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HOARE-PARTITION(A, p, r)
  x = A[p]
  i = p – 1
  j = r + 1
  while TRUE
  repeat
    j = j – 1
  until A[j] ≤ x
  repeat
    i = i + 1
  until A[i] ≥ x
  if i < j
    exchange A[i] with A[j]
  else return j

7.1-3

算法PARTITION仅有一个轮数为\(r-p\)的for循环，在第3行。其余代码都是常数时间的操作，因此算法PARTITION的时间复杂度为\(\Theta(r-p)=\Theta(n)\)。

7.1-4

1
2
3
4
5
6
7
8
9
PARTITION-DECREASE(A, p, r)
  x = A[r] // the pivot
  i = p – 1 // highest index into the low side
  for j = p to r – 1 // process each element other than the pivot
    if A[j] ≥ x // does this element belong on the low side?
      i = i + 1 // index of a new slot in the low side
      exchange A[i] with A[j] // put this element there
  exchange A[i + 1] with A[r] // pivot goes just to the right of the low side
  return i + 1