Python：将列表作为参数传递，以便对实际列表进行排序

Question

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

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)

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

Answer 1

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

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

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

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.

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

请注意，这与上面的 L[:] = result 版本并没有什么不同；这实际上只是使用 L 本身以及开始和停止索引来代替过程前半部分的副本，然后仅在合并过程的末尾进行复制。

Python：将列表作为参数传递，以便对实际列表进行排序

Python: Passing a list as parameter so the actual list is sorted

python

sorting

mergesort

list

call-by-value