0

我收到此错误：

Traceback (most recent call last):
  File "Lab1.py", line 24, in <module>
    b = mergesort(a)
  File "Lab1.py", line 19, in mergesort
    left = mergesort(lst[:middle])
  File "Lab1.py", line 21, in mergesort
    return merge(left, right)
  File "Lab1.py", line 12, in merge
    result.append(right[j])
IndexError: list index out of range

...在此代码上：

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:
            j += 1
    result.append(right[j])
    return result

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]
b = mergesort(a)
print('Input #1: ' + ', '.join(str(x) for x in a))
print('Output #1: ' + ', '.join(str(x) for x in b))

我正在使用Python 3.3.2。

4

1 回答 1

2

你1在jwhile循环中添加；如果j = len(right) - 1你最终得到j = len(right)并且那不是一个有效的索引；列表的索引必须在范围内[0, length)（0包括在内，length 排除在外）。

在循环中递增之前追加j，并用余数（已经排序）扩展结果：

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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

切片永远不会引发IndexError; 如果索引超出可用值，则返回空列表。至少其中一个left[i:]和right[j:]将是一个空列表。

演示：

>>> a = [3,1,2,5,9,6,7]
>>> b = mergesort(a)
>>> print('Input #1: ' + ', '.join(str(x) for x in a))
Input #1: 3, 1, 2, 5, 9, 6, 7
>>> print('Output #1: ' + ', '.join(str(x) for x in b))
Output #1: 1, 2, 3, 5, 6, 7, 9
于 2013-09-06T09:22:14.427 回答