Python的快速排序递归深度

我试图找到递归函数多远下降即递归的最深层次，在下面的快速排序的代码，我已被告知编辑qsort函数和希望得到任何帮助Python的快速排序递归深度

def partition(lst, lo, hi): 
    part = lo 
    while lo < hi: 
      while lst[lo] <= lst[part] and lo < hi: 
       lo += 1 
      while lst[hi] > lst[part]: # Don't have to check for hi >= 0 cos part is there as a sentinel. 
       hi -= 1 
      if lo < hi: 
       # Swap the two entries 
       lst[hi], lst[lo] = lst[lo], lst[hi] 
     # Swap part into position 
    if lst[part] > lst[hi]: # (this may happen of the array is small (size 2)) 
      lst[part], lst[hi] = lst[hi], lst[part] 
    print(part) 
    return hi 
def rec_qsort(lst, lo, hi): 
    if lo < hi: 
     pivot = partition(lst, lo, hi) 
     rec_qsort(lst, lo, pivot - 1) 
     rec_qsort(lst, pivot + 1, hi) 
def qsort(lst): 
    rec_qsort(lst, 0, len(lst) - 1) 
    return lst

来源

2016-11-18 Alex

您不会从'qsort'返回任何内容。 –

固定，我对列表本身不感兴趣，但qsort函数的递归深度。 – Alex

将深度作为可选参数传递给您的实现函数rec_qsort，默认为0。当你递归的时候加一个。

def function(data, depth=0): 
    if len(data) > 1: 
     mid = len(data)/2 
     function(data[:mid], depth+1) 
     function(data[mid:], depth+1) 
    print "depth", depth, "length", len(data), data 

data = range(10) 
function(data)

显然在一开始，如果你想看到调用的顺序，在年底通过，当他们返回打印，如果你希望他们才能打印。如果您只想在调试时看到深度，请添加手表而不是打印。

来自用户pjs：直接测量的quicksort的最大深度可以是log（n）和n之间的任何值。随机数据或随机选择数据的预期深度与log（n）成正比

来源

2016-11-18 19:07:56

Python的快速排序递归深度

回答

相关问题