0

我写了一个合并排序函数并认为我已经完成了..但在作业中它说该函数应该对实际列表进行排序而不是创建一个副本（所以我认为是按值调用而不是引用？）。现在，它不起作用，因为列表本身没有改变。

def mergeSort(L, ascending = True):
    print('Mergesort, Parameter L:')
    print(L)
    result = []
    if len(L) == 1: 
        return L 
    mid = len(L) // 2 
    teilliste1 = mergeSort(L[:mid], ascending)
    teilliste2 = mergeSort(L[mid:], ascending)
    x, y = 0, 0
    while x < len(teilliste1) and y < len(teilliste2): 
        if (ascending and teilliste1[x] > teilliste2[y]) or (not ascending and teilliste1[x] < teilliste2[y]):
            result.append(teilliste2[y])  
            y = y + 1  
        else:
            result.append(teilliste1[x]) 
            x = x + 1  
    result = result + teilliste1[x:] 
    result = result + teilliste2[y:]
    return result

liste1 = list([3, 2, -1, 9, 17, 4, 1, 0])
mergeSort(liste1)
print(liste1) # result will be the unsorted list

我需要在函数中更改什么以使其按值调用并对实际列表进行排序？

我知道我能做到

mergeResult = mergeSort(liste1)
print(mergeResult)

但显然我必须更改原始参数列表。

4

1 回答 1

2

编写递归分解函数有两种基本方法。不可变版本调用两个较小部分的副本，然后重新组合并返回它们；那是你写的。可变版本在实际输入上调用自身，然后就地修改它，并且不返回任何内容；这就是你的老师想要的。

请注意，与其他一些排序算法不同，mergesort 不能使用恒定的额外存储来完成，它只比线性额外存储好。（对数是可能的，但很复杂；我怀疑您的老师是否坚持这样做。）因此，您在书籍、维基百科等中找到的大多数合并排序算法将被编写为复制排序而不是就地排序。这意味着这可能是一个“技巧问题”，试图看看您是否可以弄清楚如何从算法的众所周知的复制版本转换为具有显式额外存储的就地版本。

您总是可以编写一个不可变的算法，然后在最后进行变异，例如：

def _mergesort(L, ascending):
    # your existing code

def mergesort(L, ascending=True):
    L[:] = _mergesort(L, ascending)

这给您带来了不变性的所有成本，而没有好处。但这确实意味着您可以使用相同的 API 编写各种排序函数，如果这是一个合理的优化，它们都可以就地实现，但如果不是，则不是，这似乎是您的老师所追求的。

如果你不想要一个包装函数，你可以改变最后一行：

return result

… 至：

L[:] = result

但是，由于这会更改 API，因此您还需要更改递归调用以匹配。例如，您可以这样做：

teilliste1 = L[:mid]
mergeSort(teilliste1, ascending)
teilliste2 = L[mid:]
mergeSort(teilliste2, ascending)

在 Python 中，变异递归分解函数通常通过将开始和结束索引与列表一起向下传递来工作，如下所示：

def mergesort(L, ascending=True, start=None, stop=None):
    if start is None: start = 0
    if stop is None: stop = len(L)

    if stop - start <= 1:
        return

    mid = (stop - start) // 2 + start 
    mergeSort(L[start:mid], ascending)
    mergeSort(L[mid:stop], ascending)

    # etc.

如上所述，合并步骤将需要一些辅助存储。做的最简单的事情——并且可能对你的分配足够好，即使它意味着线性空间——就是建立一个左列表和一个右列表，然后将它们分配回L[start:mid], L[mid:stop] = left, right.

L[:] = result请注意，这与上面的版本并没有什么不同；这实际上只是一个使用L自身以及开始和停止索引的问题，在过程的前半部分代替副本，然后在合并期间仅在结束时复制。

于 2018-06-11T17:48:34.637 回答