为什么 "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 生成了一个生成器，而生成器是惰性的，您的递归调用实际上不进行任何排序；它们只是 return 个生成器，在您遍历它们之前它们不会做任何工作。你的整个函数也只产生一个列表，因为它只包含一个 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]

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

Why is "yield" keyword not producing the expected generator in my application? (Merge sort algorithm)

python

algorithm

mergesort

yield

generator

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

Why is "yield" keyword not producing the expected generator in my application? (Merge sort algorithm)

python

algorithm

mergesort

yield

generator

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