变量的值在递归期间意外更改（MERGE SORT）

Question

给定一个输入数组：

[49, 86, 78]

我的代码应该 return:

[[49,1],[78,2],[86,1]]

即在每个子数组中，按照第一个数对数组进行排序，第二个作为索引，以备后用。我决定使用合并排序进行排序。这是我的代码（我知道它很丑但请运行它一次）：

def merge_sort(array):
    print("array>>>", array)
    if len(array[:,0]) == 1:
        print('going back')
        return
    arrL = array[0:int(len(array)/2),:]
    arrR = array[int(len(array)/2):,:] 
    print('left>>', arrL, 'right>>', arrR)
    print("*****************")
    print('into left')
    merge_sort(arrL)
    print("*****************")
    print('into right')
    merge_sort(arrR)
    print("*****************")
    print('into MERGE')
    merge(array, arrL, arrR)
    print('going back')

def merge(A, arrL, arrR):
    print("array ", A, "left", arrL, "right", arrR)
    i = 0
    while len(arrL[:,0]) is not 0 and len(arrR[:,0]) is not 0:
        print('ARRAYLEFT>>', arrL, 'ARRAYRIGHT>', arrR)
        if arrR[0,0] < arrL[0,0]:
            print(arrR[0,0], 'is less than', arrL[0,0])
            A[i] = arrR[0]
            arrR = arrR[1:,:]
            print('A>>', A, 'arrR>>', arrR, 'ARRAYLEFT>>', arrL)
        else:
            print(arrL[0,0], 'is less than', arrR[0,0])
            A[i] = arrL[0]
            arrL = arrL[1:,:]
            print('A>>', A, 'arrL>>', arrL)
        i += 1

    print('ARRAYLEFT>>', arrL, 'ARRAYRIGHT>>', arrR)

    if len(arrL[:,0]) == 0 :
        print('left exhaused')
        print('A>>', A, 'arrR>>', arrR)
        A[i:,:] = arrR
        print('A>>', A, 'arrR>>', arrR)

    elif len(arrR[:,0]) == 0:
        print('right exhaused')
        print('A>>', A, 'arrL>>', arrL)
        A[i:,:] = arrL
        print('A>>', A, 'arrL>>', arrL)

    print('after merge', A)
    return

import numpy as np
np.random.seed(1)
input_array = [np.random.choice(np.arange(100)) for _ in range(5)]
print(input_array)

输出：

[37, 12, 72, 9, 75]

然后，

new_array = np.array(list( map(list, zip(input_array, [x for x in range(len(input_array)) ])) ))
print(new_array)

输出：

array([[37,  0],
       [12,  1],
       [72,  2],
       [ 9,  3],
       [75,  4]])

最后，

merge_sort(new_array)

给出以下内容（我只添加了感兴趣的部分）。 请注意，一旦我们进行 into MERGE，一旦 arrR 变为 []，arrL 的值将更改为 arrR 的值，在代码中用 <<<=== 符号标记：

array>>> [[37  0]
 [12  1]
 [72  2]
 [ 9  3]
 [75  4]]
left>> [[37  0]
 [12  1]] right>> [[72  2]
 [ 9  3]
 [75  4]]
*****************
into left
array>>> [[37  0]
 [12  1]]
left>> [[37  0]] right>> [[12  1]]
*****************
into left
array>>> [[37  0]]
going back
*****************
into right
array>>> [[12  1]]
going back
*****************
into MERGE
array  [[37  0]
 [12  1]] left [[37  0]] right [[12  1]]
ARRAYLEFT>> [[37  0]] ARRAYRIGHT>> [[12  1]]  <<<=== # arrL = [[37  0]]
12 is less than 37
A>> [[12  1]
 [12  1]] arrR>> [] ARRAYLEFT>> [[12  1]]
ARRAYLEFT>> [[12  1]] ARRAYRIGHT>> []       <<<=== # arrL = [[12  1]]
right exhaused
A>> [[12  1]
 [12  1]] arrL>> [[12  1]]
A>> [[12  1]
 [12  1]] arrL>> [[12  1]]
after merge [[12  1]
 [12  1]]
going back
*****************
## .... and so one....

每当代码进入 into MERGE 和 arrR = [] 时似乎都会发生此错误，所以在此之后

print(new_array)

输出：

array([[ 9,  3],
       [ 9,  3],
       [ 9,  3],
       [ 9,  3],
       [75,  4]])

这显然是错误的答案。请帮助我了解我在哪里犯了错误......我已经盯着代码和输出看了整整 20 分钟，但似乎找不到它。任何 suggestion/criticism 将不胜感激。

Answer 1

这有点难理解，主要是不同地方的打印信息相似。这个问题似乎与 A[0] 和 arrL 是相同的数组这一事实有关。普通 python 列表不会出现这种情况，但 numpy 似乎做了某种优化以节省内存。所以当你修改A[i] = arrR[0]的时候，基本上就是赋值arrL = arrR。除此之外，合并排序算法的实现似乎很不寻常。您既不需要 NumPy 也不需要二维数组，只需一个数字列表即可进行排序。如果你只想要一个排序列表，你可以使用内置的实现，sorted(array)。最后，我建议您习惯调试器（在您的 IDE 或 PDB https://realpython.com/python-debugging-pdb/ 中）而不是打印语句，这是了解代码正在做什么的更有效的方法。一开始可能很难，但相信我，它会带来回报并帮助您作为开发人员取得进步。注意安全。

Answer 2

到处添加 .copy() 解决了我的问题。

def merge(A,arrL,arrR):
    i = 0
    while len(arrL[:,0]) is not 0 and len(arrR[:,0]) is not 0:
        if arrR[0,0] < arrL[0,0]:
            A[i] = arrR[0].copy()
            arrR = arrR[1:,:].copy()
        else:
            A[i] = arrL[0].copy()
            arrL = arrL[1:,:].copy()
        i+=1

    if len(arrL[:,0]) == 0 :
        A[i:,:] = arrR.copy()

    elif len(arrR[:,0]) == 0:
        A[i:,:] = arrL.copy()

    return 

def merge_sort(array):
    if len(array[:,0]) == 1:
        return
    arrL = array[0:int(len(array)/2),:].copy()
    arrR = array[int(len(array)/2):,:] .copy()
    merge_sort(arrL)
    merge_sort(arrR)
    merge(array,arrL,arrR)

变量的值在递归期间意外更改（MERGE SORT）

Variable's value changing unexpectedly during recursion (MERGE SORT)

python

recursion

mergesort