Как выполнять практику такого рода?

def combine (l1,l2):
    if l1 == []:
        return l2
    if l2 == []:
        return l1
    if l1[0] <= l2[0]:
        return [l1[0]] + combine(l1[1:], l2)
    return [l2[0]] + combine(l1, l2[1:])

Я пытаюсь попрактиковаться в определении функции с именем «sort», чтобы рекурсивно объединить список и вернуть новый список (не изменяя аргумент), который содержит каждое значение из своего списка аргументов, но в отсортированном / неубывающем порядке.

def sort(l):
    if l == []:
        return []
    else:
        l1, l2 = l[0:int(len(l)/2)], l[int(len(l)/2):]
        s = combine(l1, l2)
        return sort(s)

Однако это всегда дает мне ошибку:

RuntimeError: maximum recursion depth exceeded in comparison

python recursion sorting mergesort
person Frog_Aurora    schedule 03.05.2016    source источник
comment
Этот тип сортировки называется сортировкой слиянием.   -  person Akshat Mahajan    schedule 03.05.2016
comment
Возможный дубликат Python - рекурсивный алгоритм сортировки слиянием   -  person Akshat Mahajan    schedule 03.05.2016

Ответы (1)


arrow_upward
2
arrow_downward

Ваша функция sort рекурсивно вызывает себя с вводом одного и того же размера снова и снова, если l имеет какие-либо элементы. В конечном итоге это приведет к RuntimeError. Если вы измените свою функцию, чтобы разделить заданный list на два, сортировать половинки и объединить результат, он будет работать так, как ожидалось:

def merge_sort(l):
    if len(l) <= 1:
        return l

    return combine(merge_sort(l[0:len(l)/2]), merge_sort(l[len(l)/2:]))

Поскольку указанная выше функция разделяет заданный list на два, рекурсия в конечном итоге завершится, когда len(l) <= 1.

person niemmi    schedule 03.05.2016