Сортировка слиянием с использованием двух рекурсивных функций, а не одной рекурсивной и одной итерационной - PullRequest
Новая
       22

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

0 голосов
/ 27 мая 2019

Я пытался использовать разделяй и властвуй, чтобы создать алгоритм сортировки слиянием. Он состоит из рекурсивной функции слияния, которая, я уверен, верна, но в ней она вызывает функцию слияния, которая также рекурсивна, но не работает. Поэтому мне было интересно, если кто-нибудь может помочь мне исправить это так, чтобы это работало. Я видел другие решения для определения слияния с использованием циклов while и т. Д., И я получил идею, но хочу посмотреть, можно ли вместо этого рекурсивно писать функцию слияния.

В тот момент, когда я реализую код, я просто получаю пустой массив, который разочаровывает. 

def mergesort(A):
    length_A = len(A)
    if length_A > 1:
        return merge(
            mergesort(A[0:length_A//2]),
            mergesort(A[length_A//2 + 1:length_A-1]))
    else:
        return A

def merge(x,y):
    length_x = len(x)
    length_y = len(y)
    if length_x == 0:
        return x
    if length_y == 0:
        return y

    if x[0] <= y[0]:
        return x[0] + merge(x[1:length_x -1],y[0:length_y -1])
    else:
        return y[0] + merge(x[0:length_x-1],y[1:length_y -1])

A = [10, 2, 5, 3, 7, 13, 1, 6]
a = mergesort(A)
print(a)

1 Ответ

1 голос
/ 27 мая 2019

Две вещи:

При слиянии, если один из списков, которые должны быть объединены, пуст, вы не хотите возвращать этот список, вы хотите вернуть другой, потому что это тот, с остальными значениями. Другими словами, это назад: 

if length_x == 0:
    return x

if length_y == 0:
    return y

Должно быть: 

if length_x == 0:
    return y

if length_y == 0:
    return x

Также вы пытаетесь объединить целые и списки следующим образом: 

# x[0] is a number
return x[0] + merge(x[1:length_x -1],y[0:length_y -1])

Что-то вроде этого может быть немного лучше: 

def mergesort(A):
    length_A = len(A)
    split = length_A // 2

    if length_A > 1:
        return merge(mergesort(A[0:split]), mergesort(A[split:]))
    else:
        return A


def merge(x,y):
    if len(x) == 0:
        return y

    if len(y) == 0:
        return x

    if x[0] <= y[0]:
        return [x[0]] + merge(x[1:], y)
    else:
        return [y[0]] + merge(x, y[1:])


A = [10,2,5,3,7,13,1,6]
a = mergesort(A)
print(a)

результат 

[1, 2, 3, 5, 6, 7, 10, 13]
...