如何使用遞歸實現插入排序，哪個更有效？

我的代碼：

def insertionSort(array): 
    '''(list) - > list 
    Returns a sorted list of integers by implementing 
    the insertion sort which returns numbers in array from 
    least to greatest 
    ''' 
    for i in range(1, len(array)): 

     if array[i-1] > array[i]: #Finds a number out of place 
      temp = array[i] 
      for a in range(0,i): 
       if temp < array[a]: 
        array.insert(a,temp) 
        del array[i+1] 
        break 
    return array

來源

2013-03-23 Jacob Worldly

不，使用遞歸不是更有效率，它通常成本更高，您是否也嘗試過自己實現遞歸？ – jamylak 2013-03-23 05:45:06

@jamylak Python不會優化遞歸，而且這也相當多？我在這裏看過一些關於時間測量的帖子，這些測試結果表明，這些測試幾乎與遞歸和迭代相當。 – asheeshr 2013-03-23 05:48:07

@AshRj你在說什麼職位？ Python遞歸非常慢 – jamylak 2013-03-23 05:49:00

任何for循環for x in range(a,b): Body可以用尾遞歸重新實現：

def rfor(b, x = a): 
    if a < b: 
    Body 
    rfor(b, x + 1)

這應該給你足夠自己得到答案。在標準的Python中，這肯定比循環慢，並且每次迭代吃一個堆棧幀。在其他語言和具有良好尾部呼叫優化的實現中，它們的成本是相同的。顯然Guido has said he's uninterested in tail call optimization。

來源

2013-03-23 06:11:35 Gene

一個簡單的遞歸版本：

def insertionSort(array,i=1): 
    if i >= len(array): 
    return array 
    if array[i-1] > array[i]: 
    temp = array[i] 
    for a in range(0, i): 
     if temp < array[a]: 
     array.insert(a,temp) 
     del array[i+1] 
     break 
    return insertionSort(array, i+1)

一般遞歸是某些數據結構如樹和鏈表更好。有時候用遞歸來解決問題比較容易。我不記得遞歸實際用於效率的情況。

來源

2013-03-23 06:32:20 perreal

如何使用遞歸實現插入排序，哪個更有效？

回答

相關問題