Python:MergeSort 数据输入

Question

我想制作一个 MergeSort 算法，我想从外部文件(如 txt)获取我的数据，当我导入我的文件时，我得到一些奇怪的结果 [9. 9. 9. 9.] 我的输入数据是 [12, 44, 11, 9] 我认为这是因为 numpy 导入，但我不确定。

import numpy as np
x = np.genfromtxt("data/123.txt", delimiter=',')

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = x
mergeSort(alist)
print(alist)

Answer 1

您可以调试并注意合并 [11] 和 [9] 得到 [9,9]。

这是因为你的“列表”是真正的numpy数组，并在这里切片

    lefthalf = alist[:mid]
    righthalf = alist[mid:]

在父对象的某个位置创建一个 View (引用)，而不是数组的新实例。这就是为什么 alist[k]=righthalf[j] 操作会覆盖 lefthalf 中的 11 值的原因

All arrays generated by basic slicing are always views of the original array.

最简单的解决方法是将 ndarray 转换为标准列表:

x = list(np.genfromtxt("e:/123.txt", delimiter=','))

但更可靠的方法是通过创建新数组来重写代码。