python - 列表在合并排序的递归循环中创建后返回无类型

Question

我试图通过自己编写算法来理解算法。在尝试复制合并排序时，我遇到了一些麻烦:left & right 返回 none-type 并且在第一个 while 循环中为 len(left) 引发了错误。我一直在与代码作斗争，无法弄清楚我错过了什么？它不应该只是循环直到左右列表的大小减少到 1，这将允许它们退出 if 循环并继续函数的下一部分吗？

def merge_sort(A):

    if len(A) < 2:
        return A
    else:
        mid= len(A)//2
        left= merge_sort(A[:mid])
        right= merge_sort(A[mid:])

    i = j = 0
    sortedlist = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sortedlist.append(left[i])
            i+=1
        else:
            sortedlist.append(right[j])
            j+=1
    while i < len(left):
        sortedlist.append(left[i])
        i+=1
    while j < len(right):
        sortedlist.append(right[j])
        j+=1
    print(str(sortedlist))

Answer 1

您需要做的就是添加一条返回语句(下面代码中的最后一条语句):

def merge_sort(A):

    if len(A) < 2:
        return A
    else:
        mid= len(A)//2
        left = merge_sort(A[:mid])
        right = merge_sort(A[mid:])

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

    # NEED TO RETURN THE LIST HERE!
    return sortedlist

如果您的函数不返回任何语句，例如 left = merge_sort(A[:mid]) 会将 None 分配给 left 而不是排序的(一半)列表。

然后您可以使用以下方法进行测试:

import random

lst = list(range(15))
random.shuffle(lst)
ret = merge_sort(lst)
print(ret)