python - 如何创建一个自下而上的合并排序函数来改变输入列表？

Question

我正在尝试按照此维基百科页面上的第二个示例的方式在 Python 中实现自下而上的合并排序(据说是用“类似 C 的代码”编写的):

https://en.m.wikipedia.org/wiki/Merge_sort

我创建了一个可以运行的脚本，但是当我尝试将其封装在函数中时，该函数无法改变输入列表。改变输入列表是我想要它做的事情。

有人知道为什么我的函数 BottomUpMergeSort 无法更改输入列表吗？我知道不建议使用嵌套 while 循环，但第一个脚本似乎工作正常。非常感谢。

我的第一个脚本，它改变列表 A:

import random

A = list(range(10))
random.shuffle(A)

def Merge(a, b, start, mid, end):
    i = start
    j = mid
    for k in range(start, end):
        if i < mid and (j >= end or a[i] <= a[j]):
            b[k] = a[i]
            i += 1
        else:
            b[k] = a[j]
            j += 1

print(f'A: {A}')
# 'A: [3, 4, 5, 1, 8, 7, 2, 9, 0, 6]'

n = len(A)
B = A[:]
width = 1
while width < n:
    start = 0
    while start < n:
        mid = min(n, start + width)
        end = min(n, start + (2 * width))
        Merge(A, B, start, mid, end)
        start += 2 * width
    A = B[:]
    width *= 2

print(f'A: {A}')
# 'A: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]'

我的第二个脚本，它不会改变列表 A:

import random

A = list(range(10))
random.shuffle(A)

def Merge(a, b, start, mid, end):
    i = start
    j = mid
    for k in range(start, end):
        if i < mid and (j >= end or a[i] <= a[j]):
            b[k] = a[i]
            i += 1
        else:
            b[k] = a[j]
            j += 1

print(f'A: {A}')
# 'A: [1, 9, 5, 3, 4, 8, 7, 6, 0, 2]'

def BottomUpMergeSort(a):
    n = len(a)
    b = a[:]
    width = 1
    while width < n:
        start = 0
        while start < n:
            mid = min(n, start + width)
            end = min(n, start + (2 * width))
            Merge(a, b, start, mid, end)
            start += 2 * width
        a = b[:]
        width *= 2

BottomUpMergeSort(A)

print(f'A: {A}')
# 'A: [1, 9, 5, 3, 4, 8, 7, 6, 0, 2]'

如您所见，第一个脚本更改了 A，而第二个脚本则没有。

Answer 1

问题来自这一行:

    a = b[:]

通过在 BottomUpMergeSort 中将某些内容分配给 a，可以使其成为该函数的局部变量。因此，当您退出该函数时，您分配给此本地 a 的列表就会被丢弃。

如果您希望原始列表发生变异，只需对其进行变异即可。这里一个简单的方法是分配给一个切片，如下所示:

    a[:] = b[:]

这样，原始 a 的所有值都会被替换，但您不会创建新对象。

修改后代码的输出:

BottomUpMergeSort(A)
print(A)

# A: [8, 9, 4, 7, 1, 3, 6, 2, 5, 0]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]