Python - TypeError при реализации алгоритма сортировки слиянием - PullRequest
Новая
       28

Python - TypeError при реализации алгоритма сортировки слиянием

1 голос
/ 01 мая 2020

Итак, я новичок в python и сейчас изучаю манипуляции со списком. Ниже приведена программа, которую я написал для выполнения сортировки слиянием в моем списке. Однако во время компиляции я получаю сообщение об ошибке в строке 3- 

while len(lista) != 0 and len(listb) != 0:
    TypeError: object of type 'NoneType' has no 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)

Ответы [ 3 ]

1 голос
/ 01 мая 2020

Ваш код сбивает с толку и имеет недостатки:

  • функция сортировки называется merge, а функция объединения называется mergesort. Это полная противоположность любой реализации classi c.

  • функция слияния не возвращает ничего, поэтому lista и listb устанавливаются равными None из рекурсивного вызывает и mergesort применяет len к аргументам, которые не являются списками.

Вот измененная версия: 

def merge(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

    return listc

def mergesort(list):
    if len(list) < 2:
        return list
    else:
        mid = len(list) // 2
        lista = mergesort(list[:mid])
        listb = mergesort(list[mid:])
        return merge(lista, listb)

list = [15, 12, 14, 17, 13, 11, 12, 16, 15]
mergesort(list)
0 голосов
/ 01 мая 2020

Это потому, что в вашей функции слияния lista и listb становятся None и передаются в функцию. Также ваша функция merge_sort неверна. Вы можете обработать свою ошибку, используя следующий код: 

def mergesort(lista, listb):
    listc = []
    if not lista or not listb:
        return None
    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)
0 голосов
/ 01 мая 2020

Во-первых, не используйте list в качестве идентификатора.

В вашей функции слияния, в блоке else вы возвращаете то, что возвращается функцией слияния. А в функции слияния вы ничего не возвращаете.

Кроме того, из-за рекурсии в функции слияния вы заканчиваете тем, что устанавливаете переменные lista и listb для возвращаемых значений функции слияния, которые могут отсутствовать. поскольку mergesort ничего не возвращает (таким образом, None).

Когда вы отправляете эти lista и listb в mergesort в качестве аргументов, вы фактически отправляете None в таких случаях, и, таким образом, вы получаете ошибку, когда пытаетесь получить их длину с помощью функции len.

Чтобы устранить ошибку, вы можете отправить измененные результаты для слияния или работать со списком, который доступен в области действия обеих функций.

...