合併排序問題 - 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]，這是正確的。