python-3.x - 为什么我的合并排序算法不起作用？

Question

我正在用 Python 实现归并排序算法。以前，我在 C 中实现了相同的算法，在那里工作得很好，但是当我在 Python 中实现时，它输出一个未排序的数组。

我已经重新检查了算法和代码，但据我所知代码似乎是正确的。

我认为这个问题与 Python 中的变量范围有关，但我不知道如何解决它。

from random import shuffle
# Function to merge the arrays
def merge(a,beg,mid,end):
    i = beg
    j = mid+1
    temp = []
    while(i<=mid and j<=end):
        if(a[i]<a[j]):
            temp.append(a[i])
            i += 1
        else:
            temp.append(a[j])
            j += 1
    if(i>mid):
        while(j<=end):
            temp.append(a[j])
            j += 1
    elif(j>end):
        while(i<=mid):
            temp.append(a[i])
            i += 1

    return temp



# Function to divide the arrays recursively
def merge_sort(a,beg,end):
    if(beg<end):
        mid = int((beg+end)/2)
        merge_sort(a,beg,mid)
        merge_sort(a,mid+1,end)
        a = merge(a,beg,mid,end)

    return a

a = [i for i in range(10)]
shuffle(a)
n = len(a)
a = merge_sort(a, 0, n-1)
print(a)

Answer 1

要使其正常工作，您需要稍微更改 merge_sort 声明:

def merge_sort(a,beg,end):
    if(beg<end):
        mid = int((beg+end)/2)
        merge_sort(a,beg,mid)
        merge_sort(a,mid+1,end)
        a[beg:end+1] = merge(a,beg,mid,end)  # < this line changed
    return a

为什么:

temp 被构造为不长于 end-beg+1，但 a 是初始的完整数组，如果你设法替换所有它，它很快就会变得乏味。因此，我们取 a 的“切片”并替换该切片中的值。

为什么不:

幸运的是，您的 a 没有被替换，因为 Python 的内部工作原理，解释起来有点棘手，但我会尝试。Python 中的每个变量都是引用。 a 是对变量列表 a[i] 的引用，这些变量又是对内存中常量的引用。当您将 a 传递给一个函数时，它会生成一个新的局部变量 a ，该变量指向相同的变量列表。这意味着当您将其重新分配为 a=*** 时，它只会更改 a 指向的位置。您只能通过“切片”或通过 return 语句

将更改传递到外部

为什么“切片”有效:

切片很棘手。正如我所说，a 指向其他变量的数组(基本上是 a[i])，这些变量又是对内存中常量数据的引用，当您重新分配 a slice 它逐个元素地遍历 slice 并更改那些单独变量指向的位置，但是由于内部和外部的 a 仍然指向相同的旧元素，因此更改会经历。

希望它有意义。