现在我正在阅读算法介绍,快速排序一章。它说尾递归可用于优化。
QUICKSORT'(A, p, r)
while p < r
do ▸ Partition and sort left subarray.
q ← PARTITION(A, p, r)
QUICKSORT'(A, p, q - 1)
p ← q + 1
但是,如果每次迭代的主元数为 [1,n-1] [n],则上述代码的堆栈深度将为 O(n)。
QUICKSORT (A, p, r )
while p < r
do Partition and sort the small subarray Þrst
q ← PARTITION(A, p, r )
if q − p < r − q
then QUICKSORT (A, p, q − 1)
p ← q + 1
else QUICKSORT (A, q + 1, r )
r ← q − 1
我在上面的代码中理解的是,它将首先处理长度较小的子数组。但是为什么它可以减少到 O(lgn) 呢?如果每次枢轴仍然是 [1,n-1] [n],我认为它会保持 O(n) 堆栈深度。