如何修复合并排序，因为它将我的数组恢复为未排序的数组？

Question

我试图在python中创建一个递归的合并排序函数，但是，我的代码不能工作。它首先将代码拆分为一个单元格数组，然后将它们合并并排序。但是，在合并的第二层，函数返回到尚未排序的数组。我想知道如何使我的代码适应我的排序工作。

def merge(list1, list2):
    count1 = count2 = 0
    final = []
    while count1 < len(list1) and count2 < len(list1):
        if list1[count1] <= list2[count2]:
            final.append(list1[count1])
            count1 += 1
        else:
            final.append(list2[count2])
            count2 += 1
    if count1 == len(list1):
        for i in range(count2, len(list2)):
            final.append(list2[i])
    else:
        for i in range(count1, len(list1)):
            final.append(list1[i])
    return final


def merge_sort(nums):
    if len(nums) > 1:
        list1 = nums[:len(nums) // 2]
        list2 = nums[len(nums) // 2:]
        merge_sort(list1)
        merge_sort(list2)
        print(list1,"List1")
        print(list2,"list2")
        print(merge(list1,list2),"merge")
        return merge(list1, list2)


numbers = [2, 1, 3, 4, 6, 5, 8, 7]
print(merge_sort(numbers))

当我进入[2, 1, 3, 4, 6, 5, 8, 7]时，它被分离成多个单元格。然后进行合并排序，[1,2]，[3,4]，[5,6]，[7,8]。但是，下一次合并将恢复排序。[2,1] + [3,4] = [2,1,3,4]，[6,5] + [8,7] = [6,5,8,7].它在结尾处返回[2, 1, 3, 4, 6, 5, 8, 7]。

Answer 1

总体来说，结构是正确的。但这段代码中只有三个较小的错误。

第一个是list1的错误，而不是list2。在合并函数中，while循环应该具有条件while count1 < len(list1) and count2 < len(list2):。

接下来在merge_sort函数中。在递归调用list1和list2时，需要更新merge_sort和merge_sort。目前，list1和list2总是没有排序，这就是为什么值没有移动的原因。(见下文更新)

最后，当len(Num)==1时，您忘记了基本情况。在本例中，列表已经排序了，因为只有一个值。您仍然需要返回该列表，尽管否则将不返回。

合并排序应更新为：

def merge_sort(nums):
    if len(nums) > 1:
        list1 = nums[:len(nums) // 2]
        list2 = nums[len(nums) // 2:]
        #need to update list1 and list2
        list1 = merge_sort(list1)
        list2 = merge_sort(list2)
        print(list1,"List1")
        print(list2,"list2")
        new_list = merge(list1,list2)
        print(new_list,"merge")
        return new_list
    #need a base condition
    else:
        return nums

Answer 2

在进行递归调用时

    merge_sort(list1)
    merge_sort(list2)

，这些调用生成新的list对象(当这些调用到达return语句时)，然后忽略这些对象(因为您没有对它们做任何操作)。如当前调用所示，它们不影响list1或list2的内容。(每次调用merge_sort时，list1和list2都可能引用不同的值--在这方面，递归调用与任何其他调用没有什么不同。)

您需要使用递归调用的返回值，而不是对未修改的merge和list2进行调用。

另外:您正在定义递归排序以创建一个新列表。因此，在len(nums) <= 1的情况下，仍然需要返回一个新列表。否则，当递归到达该步骤时，它将隐式返回None，当递归中的上一次调用尝试使用该非列表值进行merge时，您将得到一个异常。

Answer 3

问题是你有两个电话：

merge_sort(list1)
merge_sort(list2)

但你假设他们在适当的地方修改list1和list2，但事实并非如此.使用赋值将它们存储回原始变量：

list1 = merge_sort(list1)
list2 = merge_sort(list2)

在顶部的第一个while语句中还有一个小错误，其中count2应该与list2的长度进行比较。

while count1 < len(list1) and count2 < len(list2):