我有一个快速排序错误与无限的再诅咒

Question

我遇到问题，我的快速排序功能不断重新诅咒三个功能的最佳。我不知道它为什么这样做，我需要帮助。我在努力实践这对于我的编码类下学期，这是从去年开始的任务，我的朋友有和IM当谈到这个错误 失去这是我的快速排序功能之一：

def quick_sort (alist, function ): 
    if len(alist) <= 1: 
     return alist + [] 
    pivot, index = function(alist) 
    #print("Pivot:",pivot) 

    left = [] 
    right = [] 


    for value in range(len(alist)): 
     if value == index: 
      continue 
     if alist[value] <= pivot: 
      left.append(alist[value]) 
     else: 
      right.append(alist[value]) 
    print("left:", left) 
    print("right:", right) 

    sortedleft = quick_sort(left, function) 
    print("sortedleft", sortedleft) 
    sortedright = quick_sort(right, function) 
    print("sortedright", sortedright) 

    completeList = sortedleft + [pivot] + sortedright 

    return completeList 

#main 

alist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] 

x = quick_sort(alist, best_of_three) 
print(x) 

这是我最好的三个功能的：

def best_of_three(bNlist, nine = False): 
    rightindex = 2 
    middleindex = 1 
    if nine == False: 

     left = blist[0] 
     rightindex = int(len(blist) - 1) 
     rightvalue = int(blist[rightindex]) 
     middleindex = int((len(blist) - 1)/2) 
     middlevalue = int(blist[middleindex]) 
     bNlist.append(left) 
     bNlist.append(middlevalue) 
     bNlist.append(rightvalue) 
     BN = bNlist 
     print("Values:",BN) 
    left = bNlist[0] 
    middle = bNlist[1] 
    right = bNlist[2] 

    if left <= middle <= right: 
     return middle , middleindex 
    elif left >= middle >= right: 
     return middle, middleindex 
    elif middle <= right <= left: 
     return right, rightindex 
    elif middle >= right >= left: 
     return right, rightindex 
    else: 
     return left, 0 

#main 
bNlist = [] 
print('Best of Three') 
blist = [54,26,93,17,77,31,44,55] 
print("") 
print("List: [54,26,93,17,77,31,44,55]") 
x, index = best_of_three(bNlist) 

print("Pivot: ",x) 
print("----------------------------") 

我真的不知道为什么它一直无限重复咒骂，

还有一个名为ninther

第三功能

def ninther(bNlist): 


    stepsize = int(len(blist)/9) 
    left = 0 
    middle = left + 2 
    right = left + 2 * stepsize 

    blist[left] 
    blist[middle] 
    blist[right] 
    leftvalue = blist[left] 
    rightvalue = blist[right] 
    middlevalue = blist[middle] 

    left2 = right + stepsize 
    middle2 = left2 + 2 
    right2 = left2 + 2 * stepsize 

    blist[left2] 
    blist[middle2] 
    blist[right2] 
    left2value = blist[left2] 
    middle2value = blist[middle2] 
    right2value = blist[right2] 

    left3 = right2 + stepsize 
    middle3 = left3 + 2 
    right3 = left3 + 2 * stepsize 

    blist[left3] 
    blist[middle3] 
    blist[right3] 
    left3value = blist[left3] 
    middle3value = blist[middle3] 
    right3value = blist[right3] 

    bN3list = [] 
    bN2list = [] 
    bNlist = [] 

    bNlist.append(leftvalue) 
    bNlist.append(middlevalue) 
    bNlist.append(rightvalue) 

    bN2list.append(left2value) 
    bN2list.append(middle2value) 
    bN2list.append(right2value) 

    bN3list.append(left3value) 
    bN3list.append(middle3value) 
    bN3list.append(right3value) 

    BN3 = bN3list 
    BN2 = bN2list 
    BN = bNlist 
    print("Ninter ") 
    print("Group 1:", BN) 
    print("Group 2:", BN2) 
    print("Group 3:", BN3) 

    x = best_of_three(bNlist, True)[0] 
    c = best_of_three(bN2list, True)[0] 
    d = best_of_three(bN3list, True)[0] 
    print("Median 1:", x) 
    print("Median 2:", c) 
    print("Median 3:", d) 

    bN4list = [x,c,d] 
    print("All Medians:", bN4list) 

    z = best_of_three(bN4list, True) 


    return z[0], z[1] 

#main 

blist = [2, 6, 9, 7, 13, 4, 3, 5, 11, 1, 20, 12, 8, 10, 32, 16, 14, 17, 21, 46] 
Y = ninther(blist) 

print("Pivot", Y) 
print("----------------------------") 

我已经在里面到处找，我不能找出问题出在哪里调用三个最佳

Answer 1

总结时：引起无限递归的主要错误是，在那里best_of_three接受你不处理的情况下长度2列表。次要错误是best_of_three修改您发送给它的列表。如果我更正这两个错误，如下所示，您的代码工作。

细节：best_of_three([1, 2])返回(2, 3)，这意味着在第三个索引处的数值为2，这是错误的。这会给出一个左边的列表[1, 2]，然后在下一次递归调用quick_sort(left, function)时导致完全相同的行为。

更一般地说，问题是从长度2列表中选择三个可能值中的最佳索引的想法是不可能的，并且您没有选择如何处理该特殊情况。

如果我这种特殊情况下的代码添加到best_of_three，它涉及的是长度为2的情况下：

if len(bNlist) == 2: 
    return bNlist[1], 1 

功能best_of_three也修改bNlist。我不知道你为什么在那个函数中有bNlist.append(left)的格式。

L = [15, 17, 17, 17, 17, 17, 17] 
best_of_three(L) 
print(L) # prints [15, 17, 17, 17, 17, 17, 17, 54, 17, 55] 

我删除了append线，由于具有best_of_three修改bNlist不太可能是你想要什么，我不知道为什么这些线路在那里。但是，你应该问自己为什么他们在那里开始。可能有一些我不知道的原因。当我这样做的时候，有几个数据是你从未使用过的，所以我删除了计算这些数据的行。

然后我注意到你的代码

rightindex = 2 
middleindex = 1 
if nine == False: 
    rightindex = int(len(blist) - 1) 
    middleindex = int((len(blist) - 1)/2) 
left = bNlist[0] 
middle = bNlist[1] 
right = bNlist[2] 

这似乎没有任何意义，因为你设置rightindex和middleindex为其他值，但你仍可以访问使用旧的指数值（2和1个）。所以我删除了if nine == False块。再次问问自己，为什么你有这个代码开始，也许还有其他一些方法你应该修改这个来解释我不知道的东西。

结果是best_of_three如下：

def best_of_three(bNlist): 
    print(bNlist) 
    if len(bNlist) == 2: 
     return bNlist[1], 1 
    rightindex = 2 
    middleindex = 1 
    left = bNlist[0] 
    middle = bNlist[1] 
    right = bNlist[2] 

    if left <= middle <= right: 
     return middle , middleindex 
    elif left >= middle >= right: 
     return middle, middleindex 
    elif middle <= right <= left: 
     return right, rightindex 
    elif middle >= right >= left: 
     return right, rightindex 
    else: 
     return left, 0 

如果我用这个，你的代码不会无限递归，和它进行排序。

我不知道你为什么提到ninther，因为它似乎与你的问题无关。您应该编辑它以删除该代码。