6

这是python中的合并排序逻辑：（这是第一部分，忽略函数merge（））问题的关键是将递归逻辑转换为while循环。代码礼貌：Rosettacode 合并排序

def merge_sort(m):
    if len(m) <= 1:
        return m

    middle = len(m) / 2
    left = m[:middle]
    right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

是否有可能在 while 循环中使其成为一种动态的方式，而每个左右数组分成两个，一种指针根据左右数组的数量不断增加并将它们分解，直到只剩下单个长度大小的列表？因为每次在左侧和右侧进行下一次拆分时，数组都会不断分解，直到只剩下一个长度列表，所以左侧（left-left，left-right）和右侧（right- left,right-right) 中断会增加，直到它达到所有大小为 1 的列表。

4

4 回答 4

4

一种可能的实现可能是这样的：

def merge_sort(m):
    l = [[x] for x in m]                  # split each element to its own list
    while len(l) > 1:                     # while there's merging to be done 
        for x in range(len(l) >> 1):      # take the first len/2 lists
            l[x] = merge(l[x], l.pop())   # and merge with the last len/2 lists
    return l[0] if len(l) else []

递归版本中的堆栈帧用于存储需要合并的逐渐变小的列表。您正确地确定了在堆栈的底部，无论您要排序的任何元素，都有一个单元素列表。因此，通过从一系列单元素列表开始，我们可以迭代地构建更大的合并列表，直到我们有一个单独的排序列表。

于 2013-11-11T11:24:08.790 回答
2

应读者的要求，从基于递归的合并排序逻辑的替代方案中转贴：

消除递归的一种方法是使用队列来管理未完成的工作。例如，使用内置的collections.deque：

from collections import deque
from heapq import merge

def merge_sorted(iterable):
    """Return a list consisting of the sorted elements of 'iterable'."""
    queue = deque([i] for i in iterable)
    if not queue:
        return []
    while len(queue) > 1:
        queue.append(list(merge(queue.popleft(), queue.popleft())))
    return queue[0]
于 2013-11-18T08:39:06.457 回答
1

据说，每个递归函数都可以用非递归的方式编写，所以简短的回答是：是的，有可能。我能想到的唯一解决方案是使用基于堆栈的方法。当递归函数调用自己时，它会将一些上下文（它的参数和返回地址）放在内部堆栈上，这对您不可用。基本上，为了消除递归，您需要做的是编写自己的堆栈，并且每次进行递归调用时，将参数放入此堆栈。

有关更多信息，您可以阅读这篇文章，或参考 Robert Lafore 的“Java 中的数据结构和算法”中名为“消除递归”的部分（尽管本书中的所有示例都是用 Java 给出的，但很容易掌握主要的主意）。

于 2013-11-11T11:10:30.017 回答
0

使用上面 Dan 的解决方案并接受关于 pop 的建议，我仍然尝试消除 while 和其他不那么 Pythonic 的方法。这是我建议的解决方案： PS: l = len

我对 Dans 解决方案的疑问是，如果 L.pop() 和 L[x] 相同并且会产生冲突，例如在迭代 L 的一半长度后出现奇数范围的情况下会怎样？

def merge_sort(m):
    L = [[x] for x in m]  # split each element to its own list
    for x in xrange(l(L)):      
        if x > 0:
            L[x] = merge(L[x-1], L[x])
    return L[-1]

这可以继续进行所有的学术讨论，但我得到了递归方法的替代方法的答案。

于 2013-11-11T13:02:47.750 回答