Python - 实现合并排序算法时出现类型错误

Question

所以我是 python 新手，目前正在学习列表操作。下面是我编写的用于对列表执行合并排序的程序。但是，在编译时，我在第 3 行出现错误-

而 len(lista) != 0 和 len(listb) != 0：

    TypeError：“NoneType”类型的对象没有 len()

我怎样才能解决这个问题？

def mergesort(lista, listb):

    listc = []

    while len(lista) != 0 and len(listb) != 0:

        if lista[0] > listb[0]:

            listc.append(listb[0])

            listb.remove(listb[0])

        else:

            listc.append(lista[0])

            lista.remove(lista[0])

    if len(lista) == 0:

        listc += listb

    else:

        listc += lista

    print(listc)

def merge(list):

    if len(list) == 0 or len(list) == 1:

        return list

    else:

        mid = len(list) // 2

        lista = merge(list[:mid])

        listb = merge(list[mid:])

        return mergesort(lista, listb)

list = [15, 12, 14, 17, 13, 11, 12, 16, 15]

merge(list)

Answer 1

您的代码令人困惑且有缺陷：调用排序函数并调用merge合并函数mergesort。这与任何经典实现完全相反。合并函数不返回任何内容，因此lista并从递归调用中listb设置为并应用于不是列表的参数。Nonemergesortlen这是修改后的版本：def merge(lista, listb):&nbsp; &nbsp; listc = []&nbsp; &nbsp; while len(lista) != 0 and len(listb) != 0:&nbsp; &nbsp; &nbsp; &nbsp; if lista[0] > listb[0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; listc.append(listb[0])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; listb.remove(listb[0])&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; listc.append(lista[0])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lista.remove(lista[0])&nbsp; &nbsp; if len(lista) == 0:&nbsp; &nbsp; &nbsp; &nbsp; listc += listb&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; listc += lista&nbsp; &nbsp; return listcdef mergesort(list):&nbsp; &nbsp; if len(list) < 2:&nbsp; &nbsp; &nbsp; &nbsp; return list&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; mid = len(list) // 2&nbsp; &nbsp; &nbsp; &nbsp; lista = mergesort(list[:mid])&nbsp; &nbsp; &nbsp; &nbsp; listb = mergesort(list[mid:])&nbsp; &nbsp; &nbsp; &nbsp; return merge(lista, listb)list = [15, 12, 14, 17, 13, 11, 12, 16, 15]mergesort(list)

Answer 2

首先，不要list用作标识符。在您的合并函数中，在 else 块中，您将返回合并排序函数返回的内容。在合并排序函数中，您什么也没有返回。此外，由于合并函数中的递归，您最终会设置变量lista并返回合并函数的值，因为没有返回任何内容（因此没有），因此listb可能没有返回值。mergesort当您将这些lista和listb合并排序作为参数发送时，您实际上在这种情况下发送 None ，因此当您尝试通过len函数获取它们的长度时会出错。要消除错误，您可以将修改后的结果发送到合并，或者可以在两个函数范围内可用的列表上工作。

Answer 3

那是因为在您的合并函数中， lista 和 listb 正在变为 None 并传递给该函数您的 merge_sort 函数也不正确。您可以使用以下代码处理您的错误：def mergesort(lista, listb):&nbsp; &nbsp; listc = []&nbsp; &nbsp; if not lista or not listb:&nbsp; &nbsp; &nbsp; &nbsp; return None&nbsp; &nbsp; while len(lista) != 0 and len(listb) != 0:&nbsp; &nbsp; &nbsp; &nbsp; if lista[0] > listb[0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; listc.append(listb[0])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; listb.remove(listb[0])&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; listc.append(lista[0])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; lista.remove(lista[0])&nbsp; &nbsp; if len(lista) == 0:&nbsp; &nbsp; &nbsp; &nbsp; listc += listb&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; listc += lista&nbsp; &nbsp; print(listc)def merge(list):&nbsp; &nbsp; if len(list) == 0 or len(list) == 1:&nbsp; &nbsp; &nbsp; &nbsp; return list&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; mid = len(list) // 2&nbsp; &nbsp; &nbsp; &nbsp; lista = merge(list[:mid])&nbsp; &nbsp; &nbsp; &nbsp; listb = merge(list[mid:])&nbsp; &nbsp; &nbsp; &nbsp; return mergesort(lista,listb)list = [15, 12, 14, 17, 13, 11, 12, 16, 15]merge(list)