时间戳

首页 > 解决方案 > 如何创建一个自下而上的合并排序函数来改变输入列表？

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

问题描述

我正在尝试按照此 Wikipedia 页面上的第二个示例（据说是用“类 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，而第二个脚本没有。

标签： pythonlistwhile-loopmergesortmutability

解决方案

问题来自这一行：

    a = b[:]

通过给ain赋值BottomUpMergeSort，你可以使它成为这个函数的局部变量。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]

推荐阅读