我有一個快速排序錯誤與無限的再詛咒

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，因爲它似乎與你的問題無關。您應該編輯它以刪除該代碼。