递归调用在Python中导致IndexError：列表索引超出范围

Question

我正在练习用不同的语言编写各种排序函数。我用python编写了一个使用递归调用的bubble sort，但是我不知道如何正确地终止递归。正如我现在所拥有的，程序排序正确，但超出了我的列表参数，并触发了一个错误：IndexError:list index out of range（在第29行）[即bubblesort（randomList）]

import random
#create a list of 10 random ints between 0-99 to be sorted
def makeRandomList():
    unsortedList=[]
    for i in range(10):
        unsortedList.append(random.randrange(100))
    print unsortedList
    return unsortedList


def bubblesort(randomList):
    i=0
    while i<=len(randomList):
        if randomList[i] > randomList[i+1]:
            randomList[i], randomList[i+1] = randomList[i+1], randomList[i]
            i+=1
            if i<len(randomList):
                bubblesort(randomList)
            else: break
        else:
            i+=1
            #for testing purposes
            print randomList
    return randomList


randomList=makeRandomList()
sortedList=bubblesort(randomList)
print "sorted list: ", sortedList

Answer 1

我解决了我的问题。我的索引在列表的末尾运行（也就是说，当我是len（随机列表）时，我的程序正在寻找len（randomList+1），它没有在基本情况下终止，因为while循环是i<；=len（randomList），而它应该是i<；（len（randomList）-1）。以下是正确的解决方案：

def bubblesort(randomList):
    i=0
    while i<(len(randomList)-1):
        if randomList[i] > randomList[i+1]:
            randomList[i], randomList[i+1] = randomList[i+1], randomList[i]
            i+=1
            if i<(len(randomList)-1):
                bubblesort(randomList)
            else: break
        else:
            i+=1
            print randomList
    return randomList

Answer 2

此错误是根据最初发布的代码编辑的。

这条线做的是你期望的吗？在

randomList[-i]<[-(i+1)]

这里您只是比较元素randomlist[-i]和[-（i+1）]。[-（i+1）]只是一个整数，而不是randomlist的元素。应该是这样的

^{pr2}$

如果您试图比较列表中的元素。在

创建大小为10的随机列表的更有效方法：

创建未排序的整数列表时，请利用random.sample()，这样就不会浪费时间和空间进行迭代。在你的例子中，random.sample(range(100), 10).

Answer 3

你的inOrder函数不起作用。i是一个作用域为函数的变量，因此在开始时设置i+=1意味着在下一个递归调用中将不会将其设置为该变量。在