python - 合并排序问题 - Python

Question

我的代码有什么问题？它仅打印 vect 值的一部分。似乎 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)

Answer 1

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

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

可能(而且很可能会)i < len(left)或 j < len(right) ，因此您需要在答案后附加适当部分的后缀。使用

很容易做到

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

解释:

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

Offtop:

你正在实现归并排序，所以请有

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