为什么这种合并排序不能正常工作？

Question

我需要使用Python3实现合并排序。我把它编码了。但它没有给出正确的输出。有人能检查一下吗？ 这是我的密码

def mergeSort(A, p, r): 
    if p < r:
        q = (p + r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q+1, r)
        Merge(A, p, q, r)

def Merge(A, p, q, r):
    i = 1
    j = q+1
    k = 0
    TEMP = [0] * (r+1)

    while i <= q and j <= r:
        if A[i] <= A[j]:
            TEMP[k] = A[i]
            k += 1
            i += 1
        else:  
            TEMP[k] = A[j] 
            k += 1
            j += 1
    if (j > r) :
        for t in range(0, q-1):
            A[r-t] = A[q-t]

    for t in range(0, k-1):
       A[p+t] = TEMP[t+1]

A = [15, 16, 13, 10, 19, 18]
mergeSort(A, 0, len(A)-1)
print(A)

多谢各位

Answer 1

您执行合并的方式（对我来说）看起来很奇怪，但我会纠正您到目前为止的错误

1-i的初始化值错误，应为：

i = p

因为我是数组A中的第一个元素

2-临时数组大小的初始化值错误，应为：

(r - p + 1)

3-填充临时数组和/或替换数组元素时似乎有错误，以下是修复代码。我在first while循环之后写了一篇关于该部分的评论，以指出在那个时候需要做什么

def mergeSort(A,p,r): 
    if p < r:
        q = (p+r)//2
        mergeSort(A,p,q)
        mergeSort(A,q+1,r)
        Merge(A,p,q,r)

def Merge(A,p,q,r):
    i = p
    j = q+1
    k=0
    
    
    TEMP =  [0]*(r - p + 1)

    while i <= q and j <= r:
        if A[i] <= A[j]:
            TEMP[k] = A[i]
            k += 1
            i += 1
        else:  
            TEMP[k] = A[j] 
            k += 1
            j += 1
    
    """
        There are currently 2 cases
    1- i > q, means we exhausted left but there are elements in the right
    2- j > r, means we exhausted right but there are elements in the left
    """
    if (j > r):
        #  copy elements at the left side to temp
        while (i <= q):
            TEMP[k] = A[i]
            i += 1
            k += 1
    else:
        #  copy elements at the right side to temp
        while (j <= r):
            TEMP[k] = A[j]
            j += 1
            k += 1
    
    
    #  replace elements in A with elements in TEMP
    for t in range(k):
        A[p+t] = TEMP[t]



A = [15,16,13,10,19,18]
mergeSort(A,0,len(A)-1)
print(A)

Answer 2

错误在Merge()函数中

1. 初始化i=p和非i=1
2. while循环终止后，可能是i<q或j<r。我们也需要适应这些情况
3. 数组TEMP的大小不正确。
   已更正的合并功能：

def Merge(A,p,q,r):
    i = p
    j = q+1
    k=0
    TEMP =  [0]*(r-p+1)
    
    while i <= q and j <= r:
        if A[i] <= A[j]:
            TEMP[k] = A[i]
            k += 1
            i += 1
        else:  
            TEMP[k] = A[j] 
            k += 1
            j += 1
    while i<=q:
        TEMP[k] = A[i]
        k+=1 
        i += 1
    while j<=r:
        TEMP[k] = A[j]
        k+=1 
        j += 1

    for t in range (p,r+1):
       A[t] = TEMP[t-p]

注意：请尝试使用更有意义的变量名