合并排序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所述。作为一个经验法则，递归调用应该总是在较小的数据集上运行。