合并排序问题 - 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 

Answer 2

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]，这是正确的。