快速排序的一些疑问 #5
Description
def __quickSubSort(seq, p, r):
"""递归版本的"""
global num
num += 1
print(num)
if p < r:
# q = __partition(seq, p, r)
q = __randPartitions(seq, p, r)
__quickSubSort(seq, p, q - 1)
__quickSubSort(seq, q + 1, r)
def __quickSubSortTail(seq, p, r):
"""循环版本，模拟尾递归，可以大大减少递归栈深度，而且时间复杂度不高"""
global num
num += 1
print(num)
while p < r:
q = __randPartitions(seq, p, r)
# q = __partition(seq, p, r)
if q - r < r - q:
__quickSubSortTail(seq, p, q - 1)
else:
__quickSubSortTail(seq, q+1, r)
r = q - 1
我对比了下这两个函数的num值，发现你底下的这个版本递归深度是大于上面的递归版本的啊？是我理解错了吗？尤其是你__randPartitions版本的整整递归了几百次？是不是我测试错了？