python - python中的递归插入排序

Question

我正在尝试在 python 中编写所有排序算法的迭代和递归版本。除了我没有返回任何东西之外，这有什么问题？我的切片有问题吗？

尝试解决方案：

    def insertOne(element, aList):
    ''' Inserts element into its proper place in a sorted list aList.
        input: element is an item to be inserted.  aList is a sorted list.
        output: A sorted list.
    '''
    if len(aList) == 0:
        return [element]
    elif element < aList[0]:
        return [element] + aList
    else:
        return aList[0:1] + insertOne(element, aList[1:])





    def sort(aList):

    if len(aList) == 0:
        return []

    n = len(aList)
    if n > 1:
        sort(aList[:n - 1])
        insertOne(n, aList)




     aList = [3,2,1]

     print sort(aList)  

Answer 1

你的sort方法不对。n是 的长度aList，而不是元素。你不想把它放在列表中，这就是你正在做的事情insertOne(n, aList)。

你想要做的是：

def sort(aList):
  if len(aList)<=1:
    return aList
  else:
    return insertOne(aList[0], sort(aList[1:]))

基本上，您正在经历aList，并使用 . 将遇到的每个元素插入到正确的位置insertOne。