合并排序有问题

Question

我觉得我的算法很好，但不知道为什么我不能得到正确的输出。我认为它与递归有关，但我在调试时遇到了问题。

def merge(front, back):
    i = 0 
    j = 0 
    k = 0
    while i < len(front) and j < len(back):
        if front[i] < back[j]:
            x[k] = front[i]
            i = i+1
        else:
            x[k] = back[j]
            j = j+1
        k = k+1
            
        while(i < len(front)):
            x[k] = front[i]
            i = i +1
            k = k+1
                
        while(j < len(back)):
            x[k] = back[j]
            j = j +1
            k = k+1
        return x
    
def mergeSort(x):
    if len(x) > 1:
        front = x[:len(x)//2]
        back = x[len(x)//2:]
        mergeSort(front)
        mergeSort(back)
        merge(front,back)
       
       

x = [12,11,13,5,6,7] 
mergeSort(x)       
print(x)

输出： [5、12、11、13、6、7]

Answer 1

让您伤心的主要问题是 merge 函数中的变量 x。

请注意，当您调用 merge 时，您正在对 x 进行更改。 x 既没有在本地命名空间中定义，也没有在封闭的命名空间中定义。所以它一直在寻找，直到到达全局命名空间。全局命名空间中定义的 x 是 [12,11,13,5,6,7] 因此它正在对此 x.

进行更改

为了解决这个问题，只需将 mergeSort 中的 x 馈入 merge。由于 mergeSort 函数的递归性质，可能会发生此行为。

您可以了解有关命名空间和变量范围的更多信息here。

您的嵌套 while 循环也存在问题。在第一个 while 循环完成之前，您不想执行第二个和第三个 while 循环。第一个while循环的停止条件是front或back已经完全排序

def merge(front, back, x):
    i = 0 
    j = 0 
    k = 0
    while i < len(front) and j < len(back):
        if front[i] < back[j]:
            x[k] = front[i]
            i = i+1
        else:
            x[k] = back[j]
            j = j+1
        k = k+1
    
    #These two while loops have been moved back one indentation
    #to run after the first while loop stops
    while(i < len(front)):
        x[k] = front[i]
        i = i +1
        k = k+1
            
    while(j < len(back)):
        x[k] = back[j]
        j = j +1
        k = k+1
    return x
    
def mergeSort(x):
    if len(x) > 1:
        front = x[:len(x)//2]
        back = x[len(x)//2:]
        mergeSort(front)
        mergeSort(back)
        merge(front,back, x)       

x = [12,11,13,5,6,7] 
mergeSort(x)       
print(x) #output is [5,6,7,11,12,13] as desired

合并排序有问题

having trouble with merge sort

python

sorting

algorithm

merge

mergesort