为什么我的合并排序实现使用列表给出正确的结果，但在 numpy 数组上使用时给出不同（错误）的结果？

Question

这是我在 Python

上的实现

def merge(L, R, A):
    len_L = len(L)
    len_R = len(R)

    i = 0 # index for left array L
    j = 0 # index for right array R
    k = 0 # index for main array A

    # replace element in main array A with smaller value from either L or R
    while (i < len_L and j < len_R):
        if L[i] < R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1
        k+=1

    # replace the rest of main array A with the remianing element from either L or R
    while i < len_L:
        A[k] = L[i]
        i+=1
        k+=1
    while j < len_R:
        A[k] = R[j]
        j+=1
        k+=1

def merge_sort(A):
    if len(A) > 1: # if the element is still dividable (length > 1)
        mid_point = len(A) // 2

        L = A[:mid_point]
        R = A[mid_point:]
        

        merge_sort(L) 
        merge_sort(R)
        merge(L, R, A)

当我运行这个代码片段

import numpy as np
np.random.seed(42)
sample_array = np.arange(21)
np.random.shuffle(sample_array)
print('Unsorted array:', sample_array)
merge_sort(sample_array)
print('Sorted array:', sample_array)

我得到了这个结果

Unsorted array: [ 0 17 15  1  8  5 11  3 18 16 13  2  9 20  4 12  7 10 14 19  6]
Sorted array: [0 1 1 1 2 2 2 2 2 2 2 2 4 4 4 6 6 6 6 6 6]

我以为我的实现是错误的，但最后我尝试先将其转换为列表

import numpy as np
np.random.seed(42)
sample_array = list(np.arange(21))
np.random.shuffle(sample_array)
print('Unsorted array:', sample_array)
merge_sort(sample_array)
print('Sorted array:', sample_array)

然后我的代码突然按预期工作了

Unsorted array: [0, 17, 15, 1, 8, 5, 11, 3, 18, 16, 13, 2, 9, 20, 4, 12, 7, 10, 14, 19, 6]
Sorted array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

我想知道是什么导致了这种行为，我试着调试了一下但没有成功。谁能赐教一下？

Answer 1

Numpy 切片是原始数组的视图，而列表切片为您提供一个新的独立列表。

考虑：

a = np.array([1, 2, 3, 4, 5])

b = a[:3]
b[1] = 100

print(a)
# array([  1, 100,   3,   4,   5]) <- mutated

对比：

a = [1, 2, 3, 4, 5]

b = a[:3]
b[1] = 100

print(a)
# [1, 2, 3, 4, 5] <- unchanged

这对您的代码有重大影响，这取决于分配新列表的切片。

为什么我的合并排序实现使用列表给出正确的结果，但在 numpy 数组上使用时给出不同（错误）的结果？

Why my merge sort implementation give correct result with list but give different (wrong) result when using on numpy array?

python

algorithm

mergesort

numpy

data-structures