为什么我不能在冒泡排序中执行递归

我想在冒泡排序算法中使用递归，但结果显示函数“bu_sort”没有被递归使用。我已经在这个问题上工作了很长时间，真的不知道问题在哪里。为什么我不能在冒泡排序中执行递归

def bu_sort(input_list): 
    print("start") 
    length = len(input_list) 
    print(length) 
    for i in range(length - 2): 
     print("times") 
     if input_list[i] > input_list[i + 1]: 
      tem = input_list[i + 1] 
      input_list[i + 1] = input_list[i] 
      input_list[i] = tem 
    bu_sort(input_list[:length - 2]) 

test1 = [7,4,2,8,5,1]  
bu_sort(test1) 
print(test1)

以下为输出，只打印一个“启动”，所以我知道该功能已经执行仅一次

test1 = [7,4,2,8,5,1]  
bu_sort(test1) 
start 
6 
times 
times 
times 
times 

print(test1) 
[4, 2, 7, 5, 8, 1]

来源

2015-10-09 D_scientist

你确定这是你正在运行的确切的代码？我得到'RuntimeError：最大递归深度超过'，这是有道理的，因为你的递归永远不会终止。 – Thomas

我认为OP缺少一个基本案例。做一些像'if len（input_list）<2：return'。我能够通过在该函数内添加该块来复制OP的输出。 – bourbaki4481472

有几个失误。首先，正如我在评论中提到的，你错过了这种递归的基本情况。其次，当你执行类似a = b[:index]的操作时，a实际上是Python中的一个新列表，因此您将一个副本而不是引用传递给递归调用（如果我对此有错，请有人纠正我）。解决这两个错误给出了下面的代码。

def bu_sort(input_list): 
    return bu_sort_with_length(input_list, len(input_list)) 

def bu_sort_with_length(input_list, length): 
    if (length < 2): 
     return 
    print("start") 
    for i in range(length - 1): 
     print("times") 
     if input_list[i] > input_list[i + 1]: 
      tem = input_list[i + 1] 
      input_list[i + 1] = input_list[i] 
      input_list[i] = tem 
    bu_sort_with_length(input_list, length - 1) 

test3 = [7]  
bu_sort(test3) 
print(test3) 

test2 = [7,4]  
bu_sort(test2) 
print(test2) 

test1 = [7,4,2,8,5,1]  
bu_sort(test1) 
print(test1)

输出：

[7] 
start 
times 
[4, 7] 
start 
times 
times 
times 
times 
times 
start 
times 
times 
times 
times 
start 
times 
times 
times 
start 
times 
times 
start 
times 
[1, 2, 4, 5, 7, 8]

来源

2015-10-09 15:43:21 bourbaki4481472

非常感谢！你对我的原始代码所说的话是完全正确的。关于第二点，我尝试修改我的代码，遵循“a = b [：length -1]”的风格，并得到一个有线答案，我在这个问题上发帖 –

@D_scientist如果这个答案对你有帮助，考虑接受它 – bourbaki4481472

为什么我不能在冒泡排序中执行递归

回答

相关问题