如何通过递归实现插入排序，哪种更高效？

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

任何一个循环，比如 for x in range(a,b): Body，都可以用尾递归的方式来实现：

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

这些信息应该能帮助你自己找到答案。在标准的Python中，这种方式肯定会比循环慢，而且每次循环都会占用一个栈帧。在其他一些语言和支持良好尾调用优化的实现中，它们的性能是差不多的。显然，Guido表示他对尾调用优化不感兴趣。

Answer 2

这是一个简单的递归版本：

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)

一般来说，递归在处理某些数据结构时，比如树和链表，会更好一些。有时候，用递归的方式来思考问题会更容易。我记不起来有哪个例子是用递归来提高效率的。