2

所以我试图理解python中这个简单的合并和排序算法。这是代码：

def merge(left, right, lt):
    """Assumes left and right are sorted lists.

    lt defines an ordering on the elements of the lists.
    Returns a new sorted(by lt) list containing the same elements
    as (left + right) would contain.

    """
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
       if lt(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        while (i < len(left)):
            result.append(left[i])
            i += 1
        while (j < len(right)):
            result.append(right[j])
            j += 1
    return result

def sort(L, lt = lambda x,y: x < y):
    """Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = sort(L[:middle], lt)
        right = sort(L[middle:], lt)
        print left, right
        return merge(left, right, lt)

我得到了它想要做的事情，我理解了合并函数中的所有代码，并对排序函数有基本的了解。

我不明白排序功能的“其他”部分实际上是如何工作的。似乎它一直在递归调用 sort 函数以将越来越小的拆分列表分配给左右变量。但是，由于它在每次调用递归函数时都将新列表分配给“左”和“右”，所以最终结果不只是左和右的最小版本吗？

似乎位于递归之外的合并函数如何知道它需要合并创建的每个拆分列表？

4

2 回答 2

6

sort()是递归的，但在一定程度上。if一旦 的长度list小于 2（或等于 1），条件将中断递归：

if len(L) < 2:

维基百科实际上有一个很好的动画来展示合并排序是如何工作的：

在此处输入图像描述

基本上，merge()组合两个排序列表并返回一个排序列表。sort()递归地将您的列表分成对，并一次对这些对进行排序，在递归的每一步合并两个排序对以形成一个更大的排序列表。只看动画。它比我更善于解释。

于 2012-09-20T19:55:15.390 回答
3

你应该画出调用堆栈，看看会发生什么。

当else子句sort再次调用函数时，函数不会在那里退出。每个调用都以其中一个return语句结束。

所以你是正确的，最初的调用sort是在越来越小的列表中传递的，但是一旦长度小于 2，'sort' 就会返回列表本身。然后调用返回到原来的位置并调用printand finally merge。

尝试使用一个小清单并写下每个电话。您会看到最终merge确实会在已排序的小列表上调用（因为它们很短）。

于 2012-09-20T19:56:30.440 回答