使用Python的合并排序错误

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]

我想最后三行应该是返回后的“[1100]r[54，91]”。 这里怎么了？我知道这里面有密码interactivePython.org网站，但我想知道我在哪里犯了逻辑错误。有人能帮我吗？非常感谢！你知道吗

Answer 1

您需要决定您的mergesort代码是要修改它所传递的列表，还是要返回一个新列表。代码的顶部编写得好像它将修改列表一样。下半部分写得好像它返回一个新列表。它们都需要以相同的方式工作，否则这种方式就行不通了。你知道吗

如果您想坚持就地修改的方法，那么代码的顶部就可以了，您需要解决的只是在最后合并left和right。您需要合并到xlist，而不是合并到left。我建议对这三个列表中的每一个使用单独的索引，而不是像现在这样对left进行代价高昂的插入。你知道吗

如果要返回一个新列表，则需要更改代码的顶部。如果命中基本大小写（len(xlist) < 2），则需要返回未修改的xlist。您还需要保存递归调用的返回值，可能使用left = mergesort(left)和right = mergesort(right)。稍后的合并代码可能还可以，不过它放弃了合并排序的大部分性能优势，因为插入逻辑是O(N**2)。你知道吗

Answer 2

我花了几分钟，但我找到了。您可以正确地在左半部分和右半部分重复出现，但随后会丢弃结果并合并原始列表。更正：

    print ('              ')
    left  = mergeSort(left)
    right = mergeSort(right)

我希望你现在能看到效果。你知道吗

---

以下是产生上述输出的工作代码：

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

        print left, 'r', right

        # print "merge", left, 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]
                # print "switched", left
                slot -= 1

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

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

输出：

A Splitting [100, 1, 91, 54] 4
              
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]
[1, 100] r [54, 91]
sorted [1, 54, 91, 100] [] [100, 1, 91, 54]
[1, 54, 91, 100]