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)

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