1

我的代码有什么问题？它只打印部分向量值。似乎while循环在某个时候中断。我不明白为什么。

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []    
    result = []

    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort()
    right.sort()
    i = 0
    j = 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

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
4

2 回答 2

5

好吧，你的错误是在你的 while 循环之后

while i < len(left) and j < len(right):
  ...

可能（并且很可能会）是i < len(left)or j < len(right)，因此您需要在答案中附加适当部分的后缀。这很容易做到

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

解释：

想象一下合并过程：你有 i 和 j 在开始时为 0，并且在每一步你向前移动其中一个。你什么时候停下来？当其中一个到达终点时。假设我已经走到了尽头。因此，您将整个左侧部分添加到结果中，但是在 j 和 len(right) 之间的右侧仍有一些元素，因此您也必须将它们添加到答案中。

离顶：

您正在实施合并排序，所以请

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

代替

left.sort()
right.sort()

注意：您必须在合并函数的开头将以下检查添加到您的代码中，以避免无限递归：

if len( vect ) == 1:
   return vect

同样在您的 print_list 函数中，您可以使用

print vect

或者至少

for x in vect
print x
于 2013-02-08T17:19:57.947 回答
3

只要 left 或 right 用尽，while 循环就会退出。这使得未用尽列表中剩余的所有元素都未合并。

将您的代码更改为：

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []

    result = []
    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort();
    right.sort();
    i = 0
    j = 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

    if i < len(left):
        result.extend(left[i:])
    else:
        result.extend(right[j:])

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
print vect

如果您使用左右排序方法，我有点困惑为什么您不只是在整个列表中使用它。但我想你有你的理由。:)

编辑：我把整个代码块放在那里，这样你就可以看到它。当我运行它时，它会打印 [0, 1, 2, 3, 5, 7, 10]，这是正确的。

于 2013-02-08T17:23:06.930 回答