python - buggy 合并排序

下面是我的Merge函数，该函数类似于第31页的CLRS中所示。现在，我已经注释掉了可处理所有剩余列表项的代码。

如果我通过A = [1,2,1,2,12,2,5]作为输入。输出为[1、2、1，无，无，无]。

任何人都可以对我在做什么错一点看法吗？

def Merge(left, right):
    result = [None] * (len(left) + len(right))
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result[k] = left[i]
            #result.append(left[i])
            i += 1
        else:
            result[k] = right[j]
            #result.append(right[j])
            j += 1
        k += 1

## remaining items in remaining list
##    while i < len(left):
##        result[k] = left[i]
##        i += 1; k+= 1;
##
##    while j < len(right):
##        result[k] = right[j]
##        j += 1; k+= 1;
##
    return result

## Ref.: CLRS page 34
def MergeSort(A):
    if len(A) > 1:
        mid = int(len(A)/2)
        left = A[:mid]
        right = A[mid:]
        MergeSort(left)
        MergeSort(right)
        return Merge(left, right)
    else:
        return A

if __name__ == "__main__":
    a = [1, 2, 1, 12, 2, 5]
    print "a = %s" % a
    print "sort a = %s" % MergeSort(a)

最佳答案

调用MergeSort时，您递归地返回新列表，但是从不分配它们：

def Merge(left, right):
    result = [None] * (len(left) + len(right))
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result[k] = left[i]
            #result.append(left[i])
            i += 1
        else:
            result[k] = right[j]
            #result.append(right[j])
            j += 1
        k += 1

## remaining items in remaining list
##    while i < len(left):
##        result[k] = left[i]
##        i += 1; k+= 1;
##
##    while j < len(right):
##        result[k] = right[j]
##        j += 1; k+= 1;
##
    return result

## Ref.: CLRS page 34
def MergeSort(A):
    if len(A) > 1:
        mid = int(len(A)/2)
        left = A[:mid]
        right = A[mid:]
        #MergeSort(left)
        # here should be
        left = MergeSort(left)
        #MergeSort(right)
        # here should be
        right = MergeSort(right)
        return Merge(left, right)
    else:
        return A

if __name__ == "__main__":
    a = [1, 2, 1, 12, 2, 5]
    print "a = %s" % a
    print "sort a = %s" % MergeSort(a)

关于python - buggy 合并排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23655216/