比較錯誤python超出最大遞歸深度？

-1

即時嘗試使用mergesort來對數字列表進行排序，並比較排序方法（氣泡，選擇等）之間排序長度不同的列表所花費的時間如何不同。所以我用下面的代碼來測試：比較錯誤python超出最大遞歸深度？

k=0 
times=[] 

while k<n: 
    x=list(range(1,2**k)) 
    shuffle(x) 
    start=clock() 
    selectionsort(x) 
    end=clock() 
    times.append(end-start) 
    k=k+1 
return(times)

其中洗牌是我的洗牌排序的代碼，這將改變以歸併和選擇排序。當我測試shuffle排序和選擇排序時，代碼根據需要運行，但是當我測試mergesort時，我得到的比較錯誤超出了最大遞歸深度。我的合併代碼如下：

def mergesort(list): 
    if len(list) == 1: 
     return list 

    m = len(list)//2 
    l = mergesort(list[:m]) 
    r = mergesort(list[m:]) 

    if len(l)<1 or len(r)<1: 
     return l or r 

    result = [] 
    i = j = 0 
    while (len(result)<len(r)+len(l)): 
     if l[i] < r[j]: 
      result.append(l[i]) 
      i = i+1 
     else: 
      result.append(r[j]) 
      j = j+1 
     if i == len(l) or j == len(r): 
      result.extend(l[i:] or r[j:]) 
      break 
    return result

任何人都可以提出爲什麼我可能會得到這個錯誤？提前致謝！

來源

2016-11-20 Denis Mclaughlin

我會建議你閱讀合併排序的工作方式。它由兩個不同的功能構成 - 一個是將列表拆分成另外兩個，第二個將它們合併。 https://en.wikipedia.org/wiki/Merge_sort – Nf4r

請發佈錯誤的完整堆棧跟蹤，以及您對該函數的實際輸入。 – poke

如果傳遞的參數是空列表，則mergesort函數無法正常工作。它會永久遞歸，因爲當長度正好是1時，您的基本情況只會停止它。

由於您的驅動程序代碼在list(range(1,2**k))上運行排序代碼，並且k最初爲零，因此您會在第一次迭代中獲得一個空列表（range(1, 1)爲空）。

要解決此問題，更改排序的基本情況停止，如果列表是空的（因爲沒有什麼排序）：

def mergesort(list): 
    if len(list) <= 1: # less than or equal! 
     return list

一個進一步的建議（無關您的問題）：這是一個使用list作爲變量名非常糟糕。當你這樣做時，你掩蓋了內建的list類型，這可能會導致錯誤。一個常見的選擇是lst（但如果需要，您可以使用更具描述性的名稱）。

來源

2016-11-20 00:45:01 Blckknght

謝謝你的幫助！我相對比較新的編碼，所以任何提示都很感謝！ –

比較錯誤python超出最大遞歸深度？

回答

相關問題