合并排序 python 3

Question

我实现了这样的合并排序算法，悬停我遇到了一些问题

import sys

if __name__ == '__main__':
        input = sys.stdin.read()
        data = list(map(int, input.split()))
        n = data[0]
        a = data[1:]
        print(merge_sort(a))

def merge(left,rigt):
    result = []
    i = j = 0
    while i < len(left) and j < len(rigt):
        if left[i] <= rigt[j]:
            result.append(left[i])
            i += 1

        else:
            result.append(rigt[j])
            j += 1

    result += left[i:]
    result += rigt[j:]

    return result

def merge_sort(a):
    if len(a) <= 2:
        return 1

    middle = len(a)//2

    left = a[:middle]
    right = a[middle:]

    left = merge_sort(left)
    right = merge_sort(right)

    return list(merge(left,right))

我遇到这样的错误

TypeError: object of type 'int' has no len()

我不明白，我错在哪里，为什么程序认为 "left" 和 "right" 是 int，但它是数组。

Answer 1

您忘记了 merge_sort 函数的终止情况，即 returns 1。因此，当递归到达底部时，left 和 rigt 是 int，您需要考虑到这一点在你的代码中。

Answer 2

你应该更换

if len(a) <= 2:
    return 1

和

if len(a) == 1:
    return a

到return一个不可分区的列表。

合并排序 python 3

Merge sort python 3

python

sorting

mergesort