python - Python 中的 Mergesort，我的第一个排序算法，哪里出了问题？

Question

def mergesort(a):
    if len(a)<=1:
        return a

    else:
        mid=len(a)/2
        mergesort(a[:mid])
        mergesort(a[mid:])
        auxa=[]
        j=0
        k=mid
        while j<mid and k<len(a):
            if a[j]<a[k]:
                auxa.append(a[j])
                j+=1
            else:
                auxa.append(a[k])
                k+=1

        if j==mid:
            auxa.extend(a[k:])

        if k==len(a):
            auxa.extend(a[j:mid])

        a=auxa


        return a

testlist=[3,2,1]   
print mergesort(testlist) 

我得到的结果是 2 1 3

非常感谢任何帮助，谢谢!

Answer 1

您的函数 mergesort 返回一个新列表，并且不会像您期望的那样修改您提供的列表。因此，当您调用 mergesort(a[:mid]) 时，您得到的是这些元素的新排序版本，而原始 a[:mid]保持完全相同。

编辑:这里的问题是 python 列表切片的工作方式。当您说 a[:mid] 时，python 会创建原始文件的“副本”(不用担心副本的确切类型)。现在，当您在函数中修改此副本时，您所做的只是更改其中的引用以指向新的整数，而不是以任何方式修改原始引用。下面是一些代码来充实这一点:

def change(a):
    a[1] = 0

a = [1, 2, 3]
change(a)
a
>> [1, 0, 3]

a = [1, 2, 3]
change(a[:2])
a
>> [1, 2, 3] 

编辑 2:复制回正确完成的值(如评论中 (abamert) 所建议):

def mergesort(a):
  if len(a)<=1:
    return a

  else:
    mid=len(a)/2
    a = mergesort(a[:mid]) + mergesort(a[mid:])
    auxa=[]
    j=0
    k=mid
    while j<mid and k<len(a):
        if a[j]<a[k]:
            auxa.append(a[j])
            j+=1
        else:
            auxa.append(a[k])
            k+=1

    if j==mid:
        auxa.extend(a[k:])

    if k==len(a):
        auxa.extend(a[j:mid])


    return auxa

这显然是更好的方法，涉及的复制更少，但我认为这个解决方案与原始代码的问题更相关。