排序使用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在最後你需要修復。而不是合併到left，您需要合併到xlist。我建議在每個列表中使用單獨的索引，而不是像你目前正在做的那樣在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]