python - 如何使用递归实现插入排序，哪个更有效？

Question

我如何使用递归来实现这一点，它会更有效吗？

我的代码：

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

Answer 1

一个简单的递归版本：

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)

通常递归对于某些数据结构（例如树和链表）更好。有时用递归来解决问题更容易思考。我不记得递归实际上用于提高效率的情况。

Answer 2

任何 for 循环for x in range(a,b): Body都可以用尾递归重新实现：

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

这应该足以让您自己获得答案。在标准 Python 中，这肯定会比循环慢，并且每次迭代都会吃掉一个堆栈帧。在具有良好尾调用优化的其他语言和实现中，它们的成本是相等的。显然Guido 说他对尾调用优化不感兴趣。