合併排序python無限循環

Question

我決定最近學習python！我想那種用下面的代碼編寫一個簡單的合併：

def mergeSort(lst): 
    l = len(lst) 

    if l <= 0: 
     print("empty") 
     return None 
    elif l == 1: 
     return lst 

    half = int(l/2) 
    m = lst[half] 

    print(half, m) 

    left = [] 
    right = [] 

    for n in lst: 
     if n < m: 
      left.append(n) 
     else: 
      right.append(n) 

    left = mergeSort(left) 
    right = mergeSort(right) 

    return merge(left, right) 

不幸的代碼生成一個無限循環，當它有對付列表，如[111]。你能提出一些解決這種錯誤行爲的方法嗎？

Answer 1

您是否已退房http://www.geekviewpoint.com/？這可能是學習如何用Python編寫算法的最好方法。一探究竟。作爲一個獎勵，它是一個非常乾淨的網站，我最近看到的唯一一則廣告是關於axdlab稱爲「Puzz！」的android智能拼圖應用程序。該網站本身有各種算法和很好的解釋。

這裏是他們的歸併排序：

#======================================================================= 
# Author: Isai Damier 
# Title: Mergesort 
# Project: geekviewpoint 
# Package: algorithm.sorting 
# 
# Statement: 
# Given a disordered list of integers (or any other items), 
# rearrange the integers in natural order. 
# 
# Sample Input: [8,5,3,1,9,6,0,7,4,2,5] 
# 
# Sample Output: [0,1,2,3,4,5,5,6,7,8,9] 
# 
# Time Complexity of Solution: 
# Best = Average = Worst = O(nlog(n)). 
# 
# Approach: 
# Merge sort is a divide and conquer algorithm. In the divide and 
# conquer paradigm, a problem is broken into pieces where each piece 
# still retains all the properties of the larger problem -- except 
# its size. To solve the original problem, each piece is solved 
# individually; then the pieces are merged back together. 
# 
# For illustration, imagine needing to sort an array of 200 elements 
# using selection sort. Since selection sort takes O(n^2), it would 
# take about 40,000 time units to sort the array. Now imagine 
# splitting the array into ten equal pieces and sorting each piece 
# individually still using selection sort. Now it would take 400 
# time units to sort each piece; for a grand total of 10400 = 4000. 
# Once each piece is sorted, merging them back together would take 
# about 200 time units; for a grand total of 200+4000 = 4,200. 
# Clearly 4,200 is an impressive improvement over 40,000. Now 
# imagine greater. Imagine splitting the original array into 
# groups of two and then sorting them. In the end, it would take about 
# 1,000 time units to sort the array. That's how merge sort works. 
# 
# NOTE to the Python experts: 
#  While it might seem more "Pythonic" to take such approach as 
# 
#   mid = len(aList)/2 
#   left = mergesort(aList[:mid]) 
#   right = mergesort(aList[mid:]) 
# 
#  That approach take too much memory for creating sublists. 
#======================================================================= 
def mergesort(aList): 
    _mergesort(aList, 0, len(aList) - 1) 


def _mergesort(aList, first, last): 
    # break problem into smaller structurally identical pieces 
    mid = (first + last)/2 
    if first < last: 
    _mergesort(aList, first, mid) 
    _mergesort(aList, mid + 1, last) 

    # merge solved pieces to get solution to original problem 
    a, f, l = 0, first, mid + 1 
    tmp = [None] * (last - first + 1) 

    while f <= mid and l <= last: 
    if aList[f] < aList[l] : 
     tmp[a] = aList[f] 
     f += 1 
    else: 
     tmp[a] = aList[l] 
     l += 1 
    a += 1 

    if f <= mid : 
    tmp[a:] = aList[f:mid + 1] 

    if l <= last: 
    tmp[a:] = aList[l:last + 1] 

    a = 0 
    while first <= last: 
    aList[first] = tmp[a] 
    first += 1 
    a += 1 

下面是測試平臺：

import unittest 
from algorithms import sorting 

class Test(unittest.TestCase): 

    def testMergesort(self): 
     A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5] 
     sorting.mergesort(A) 
     for i in range(1, len(A)): 
      if A[i - 1] > A[i]: 
      self.fail("mergesort method fails.") 

Answer 2

我相信你只是應該在中點將這個列表分成兩半，而不是對每一半進入哪些項目進行排序。

因此，不是這樣的：

left = [] 
    right = [] 
    for n in lst: 
     if n < m: 
      left.append(n) 
     else: 
      right.append(n) 

只是這樣做：

left = lst[:half] 
    right = lst[half:] 

Answer 3

你實現的算法是（有瑕疵）快速排序不去除所謂的「透視」元素，在你的情況m。

您所做的合併操作不需要進行合併排序中的任何合併操作，因爲如果要正確處理數據透視表，則對mergeSort(left)的調用將已經返回排序的left。

在合併排序中，您沒有支點元素m，相反，您只需將該列表分爲兩部分，如James所述。作爲一個經驗法則，遞歸調用應該總是在較小的數據集上運行。