python - 使用Python进行归并排序的一个bug

Question

我正在使用递归 Python 进行合并排序。我找不到自己哪里出错了，而且总是得到错误的答案。代码如下:

def mergeSort(xlist):
    print ('Splitting',xlist, len(xlist))
    if len(xlist)>1:
       midpoint = len(xlist) // 2
       left  = xlist[:midpoint]
       right = xlist[midpoint:]
       print ('----------------------------')
       mergeSort(left)
       mergeSort(right)

       print (left, 'r', right)

       while len(right) >0:
          left.append(right[0])
          right.remove(right[0])
          slot= len(left)-1
          while slot >0:
              if left[slot] < left[slot-1]: left[slot], left[slot-1] = left[slot-1], left[slot]
              slot -= 1

       print ('sorted',left, right,xlist)
       return left

print('A',mergeSort([100,1,91,54])) 

合并时，输出也以错误的方式显示，例如:

 Splitting [100, 1, 91, 54] 
 ---------------------------- 
 Splitting [100, 1] 2
 ---------------------------- 
 Splitting [100] 1 
 Splitting [1] 1 
 [100] r [1] 
 sorted [1, 100] [] [100, 1]
 Splitting [91, 54] 2
 ---------------------------- 
 Splitting [91] 1 
 Splitting [54] 1 
 [91] r [54] 
 sorted [54, 91] [] [91, 54]
 [100, 1] r [91, 54] 
 sorted [1, 54, 100, 91] [] [100, 1, 91, 54]
 A [1, 54, 100, 91]

我预计返回后最后第三行应该是“[1,100] r [54, 91]”。这里有什么问题吗？我知道 InteractivePython.org 中有一段代码，但我想了解我在哪里犯了逻辑错误。谁能帮我？非常感谢!

Answer 1

您需要决定您的 mergesort 是否代码将修改它所传递的列表，或者是否将返回一个新列表。代码的顶部部分的编写方式就好像它将修改列表一样。下半部分的写法就好像它返回一个新列表一样。它们都需要以相同的方式工作，否则排序将不起作用。

如果您想坚持就地修改方法，代码的顶部部分就可以了，它只是 left 的合并。和right最后你需要修复。而不是合并到 left ，您需要合并到 xlist 。我建议在三个列表中的每一个中使用单独的索引，而不是在left中进行昂贵的插入。就像您目前正在做的那样。

如果你想返回一个新的列表，你需要更改代码的顶部部分。如果遇到基本情况( len(xlist) < 2 )，则需要返回 xlist未经修改。您还需要保存递归调用的返回值，可能使用 left = mergesort(left)和right = mergesort(right) 。您稍后的合并代码可能没问题，尽管它放弃了合并排序的大部分性能优势，因为插入逻辑是 O(N**2) .