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的快速排序遞歸深度

回答

相關問題