为什么“yield”关键字没有在我的应用程序中生成预期的生成器？（归并排序算法）

Question

为什么我的yield关键字没有产生预期的输出？

我正在使用递归算法（合并排序）并使用，yield以便每次更改（排序）时都可以遍历列表。

def MergeSort(lst):

    if len(lst) > 1:
        middle = len(lst)//2
        lefthalf = lst[:middle]
        righthalf = lst[middle:]

        MergeSort(lefthalf)
        MergeSort(righthalf)

        i,j,k= 0,0,0

        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] < righthalf[j]:
                lst[k] = lefthalf[i]
                i+=1
            else:
                lst[k] = righthalf[j]
                j+=1

            k+=1

        while i<len(lefthalf):
            lst[k]=lefthalf[i]
            i+=1
            k+=1

        while j<len(righthalf):
            lst[k]=righthalf[j]
            j+=1
            k+=1

        yield lst

a = MergeSort([2,3,566,78,8])
for i in a:
    print(i)
[2, 3, 566, 78, 8]

相反，我希望实现如下目标：（随着算法的工作）

[2, 3, 566, 78, 8]
[2, 3, 566, 8, 78]
[2, 3, 8, 78, 566]

如果我使用return语句，它将按预期工作并对列表进行排序，但是当我使用时，yield我无法获得合适的生成器。我还尝试将语句放在yield内部while以及其他几乎所有地方。我怎样才能解决这个问题？我错过了什么？

Answer 1

因为你做MergeSort了一个生成器，而生成器是懒惰的，你的递归调用实际上不做任何排序；它们只返回生成器，在您遍历它们之前不会做任何工作。你的整个函数也只产生一个列表，因为它只包含一个yield语句，而且它不在循环中，所以它只执行一次。

解决这两个问题的方法是yield from MergeSort(...)用尽您递归创建的生成器。这将耗尽它们以便它们进行排序工作，并且还会导致外部生成器生成任何内部生成器生成的生成器。因此，更改这两行：

        yield from MergeSort(lefthalf)
        yield from MergeSort(righthalf)

例子：

>>> for i in MergeSort([2, 3, 566, 78, 8]):
...     print(i)
... 
[2, 3]
[8, 78]
[8, 78, 566]
[2, 3, 8, 78, 566]

请注意，您没有看到相同长度的列表；递归调用在较短的列表中，因此它们产生较短的列表。您也没有在基本情况下看到长度为 1 的列表，因为您的yield lst语句在if len(lst) > 1:块内。如果您取消缩进该行，使其yield lst成为无条件的，您可以看到每次调用的结果：

>>> for i in MergeSort([2, 3, 566, 78, 8]):
...     print(i)
... 
[2]
[3]
[2, 3]
[566]
[78]
[8]
[8, 78]
[8, 78, 566]
[2, 3, 8, 78, 566]