0

quicksort 的朴素递归版本：

QUICKSORT(A,p,r)
 if p < r then 
   q=PARTITION(A,p,r)
   QUICKSORT(A,p,q-1)
   QUICKSORT(A,q+1,r)

这使用了 O(n) 额外空间

在 Cormen ch 7-4 "Stack depth for quick sort" 中提到
- QUICKSORT 中的第二次递归调用不是必需的，它可以通过迭代控制结构来避免。这种方法称为尾递归

修改版的快速排序：

QUICKSORT'(A,p,r)
 while p < r
   q=PARTiTION(A,p,r)
   QUICKSORT'(A,p,q-1)
   p=q-1

空间复杂度 O(log n)

我无法理解空间复杂度是如何降低的。
我不认为它的尾递归

谁能解释一下空间复杂度如何降低（调用如何使用堆栈）或任何其他更好的方法来实现这一点。

4

0 回答 0