0

我正在尝试合并排序算法，但收到此类型错误：

Input #1: [3, 1, 2, 5, 9, 6, 7]
Traceback (most recent call last):
  File "Lab1.py", line 24, in <module>
    print('Output #1: ' + mergesort(a))
  File "Lab1.py", line 18, in mergesort
    left = mergesort(lst[:middle])
  File "Lab1.py", line 20, in mergesort
    return merge(left, right)
  File "Lab1.py", line 6, in merge
    while i < len(left) and j < len(right):
TypeError: object of type 'NoneType' has no len()

...在此代码上：

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

def mergesort(lst):
    if len(lst) <= 1:
        return lst
    middle = int(len(lst) / 2)
    left = mergesort(lst[:middle])
    right = mergesort(lst[middle:])
    return merge(left, right)

a = [3,1,2,5,9,6,7]
print 'Input #1: ' + str(a)
print 'Output #1: ' + mergesort(a)
4

1 回答 1

2

您忘记了return合并功能中的 ：

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

请注意，此merge函数不正确。如果left和right具有不同的长度，则不会result包含两个列表的所有元素。（因为其中一个索引，比如，将失败when没有扫描整个列表的条件）。这总是会发生的，因为循环一次只增加一个索引，这意味着在某些时候你可以有，但只有一个和将在下一次迭代中增加，两个条件之一将是，导致循环停止。ii < len(left)jrightwhilei = len(left) - 1j = len(right) - 1ijFalse

看：

In [2]: mergesort(list(range(17)))
Out[2]: [0]

添加：

result.extend(left[i:] or right[j:])

在return应该解决这个问题之前：

In [4]: mergesort(list(range(17)))
Out[4]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
于 2013-09-06T07:01:40.317 回答