h**o
发帖数: 548 | 1 CLRS problem 7-4:
QUICKSORT using tail recursion is implemented as QUICKSORT':
QUICKSORT'(A, p, r)
1 while p < r
2 do // Partition and sort left subarray.
3 q ← PARTITION(A, p, r)
4 QUICKSORT'(A, p, q − 1)
5 p ← q + 1
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r)
3 QUICKSORT(A, p, q − 1)
4 QUICKSORT(A, q + 1, r)
请问为何QUICKSORT‘ 和QUICKSORT 是一样的哪？
in QUICKSORT()', 第一次QUICKSORT'(A, p, q − 1), 第二次
因为 p ← q + 1， QUICKSORT'(A, p, q − 1) 相当于 QUICKSORT'(A, q+1, q'
− 1)
where q' 是 [q+1,r]之间的一个数，而QUICKSORT() 中 第一次QUICKSORT(A, p, q &#
8722; 1)，
但第二次是 QUICKSORT(A, q + 1, r)。 最后一个参数是r, 不是 q'.
有谁解释下为何QUICKSORT‘ 和QUICKSORT 是一样的哪？ | I******c
发帖数: 163 | 2 in QUICKSORT()', 第一次QUICKSORT'(A, p, q − 1), 第二次
因为 p ← q + 1， QUICKSORT'(A, p, q − 1) 相当于 QUICKSORT'(A, q+1, q'
− 1)
我觉得第二次相当于 QUICKSORT'(A, q+1, r),因为是在同一个function里。我不太清
楚你的q'是如何算出来的。 | h**o
发帖数: 548 | 3 第一次QUICKSORT'后， p = q+1;
然后回line3, q = PARTITION(A, p, r)， 相当于q' = PARTITION(A, q+1, r)；
所以此时得到的新的q'一定在[q+1,r]间吧。
然后line4,QUICKSORT'(A, p, q − 1)， 相当于QUICKSORT'(A, q+1, q' −
; 1)
所以我不明白为何第二次QUICKSORT'后相当于QUICKSORT'(A, q+1, r)而不是
QUICKSORT'(A, q+1, q' − 1)?
q'
【在 I******c 的大作中提到】
: in QUICKSORT()', 第一次QUICKSORT'(A, p, q − 1), 第二次
: 因为 p ← q + 1， QUICKSORT'(A, p, q − 1) 相当于 QUICKSORT'(A, q+1, q'
: − 1)
: 我觉得第二次相当于 QUICKSORT'(A, q+1, r),因为是在同一个function里。我不太清
: 楚你的q'是如何算出来的。
| I******c
发帖数: 163 | 4 哦，我明白你说得第一次和第二次的QUICKSORT'的具体意思了。你说第二次QUICKSORT'
(A, q+1, q' − 1)实际上也是相当于QUICKSORT(A, q+1, q' − 1)的。 | h**o
发帖数: 548 | 5 明白了。
the basic idea of QUICKSORT' 是说 每次循环都 recursively sort the first part
, iterately sort the second part.
QUICKSORT'
【在 I******c 的大作中提到】
: 哦，我明白你说得第一次和第二次的QUICKSORT'的具体意思了。你说第二次QUICKSORT'
: (A, q+1, q' − 1)实际上也是相当于QUICKSORT(A, q+1, q' − 1)的。
|
|
