合并排序问题 - 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(右侧)之间仍然存在一些元素,因此您还必须将它们添加到答案中.

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