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が異なる場合、両方のリストのすべての要素が含まれているわけではありません。（インデックスの1つ、たとえば、リスト全体をスキャンしなかった場合の条件に失敗するため）。ループは一度に 1 つのインデックスしか増加させないため、これは常に発生します。つまり、ある時点でandを持つことができますが、次の反復では と の 1 つだけが増加し、2 つの条件の 1 つがになり、ループして停止します。resultii < 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 に答える