0

我最近决定学习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)

不幸的是，当它必须处理诸如 [1 1 1] 之类的列表时，此代码会生成一个无限循环。你能建议一些方法来解决这个错误的行为吗？

4

3 回答 3

4

你检查过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." )
于 2013-05-18T14:24:25.227 回答
2

我相信你只是应该在中点将列表分成两半 - 而不是对每一半的项目进行排序。

所以代替这个：

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

这样做：

   left = lst[:half]
   right = lst[half:]
于 2013-05-18T11:21:16.227 回答
1

在您的情况下，您实现的算法是（有缺陷的）快速排序，没有删除所谓的“枢轴”元素m。

您所做的合并操作不需要像在合并排序中那样进行任何合并，因为如果您要正确处理枢轴，则a 调用mergeSort(left)已经返回一个 sorted 。left

在合并排序中，您没有枢轴元素m，相反，您只需将列表分成两部分，如 James 所述。

根据经验，递归调用应始终对较小的数据集进行操作。

于 2013-05-18T11:30:07.757 回答