如何制作一个自下而上的合并排序函数来改变输入列表？

Question

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

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]

如何制作一个自下而上的合并排序函数来改变输入列表？

How can I make a bottom-up mergesort function that mutates the input list?

python

mergesort

list

while-loop

mutability