合并排序递归错误

Question

我在 python.The 函数合并中编写了这个合并排序代码，当我单独调用它时它运行良好，它对两个不同的排序 lists.But 当我在真正的合并排序递归问题中使用它时，它没有按预期进行 work.I 正在上传我的代码请帮助我解决这个问题

def merge(list,p,q,r):

    list1=[]
    list2=[]
    list3=[]
    i=0
    j=0
    for a in list[:q+1]:
        list1.append(a)
    list1.append(99999999999)

    for b in list[q+1:]:
        list2.append(b)
    list2.append(9999999999999999999999999)
    for k in range(len(list)):
        if list1[i]<list2[j]:
            list3.insert(k,list1[i])
            i=i+1
        else:
            list3.insert(k,list2[j])
            j=j+1
        return list3




def mergesort(list,p,r):

    if p<r:

      q=(p+r)/2
      mergesort(list,p,q)
      mergesort(list,q+1,r)
      merge(list,p,q,r)


list=[1,5,7,8,2,4,6,9]

mergesort(list,0,7)

print list

没有意向性错误

输出是：

[1, 5, 7, 8, 2, 4, 6, 9]

它的打印与列表相同不排序

Answer 1

您没有在函数“merge”

中修改列表

您要么需要修改 list 要么 return 新的 list ，您两者都不做

您可以 return list3 从合并功能并将合并排序修改为：

def mergesort(list,p,r):
    if p<r:
      q=(p+r)/2
      mergesort(list,p,q)
      mergesort(list,q+1,r)
      list =merge(list,p,q,r)

您好，成功了：使用

 def merge(list,p,q,r):

    list1=[]
    list2=[]
    list3=[]
    i=0
    j=0
    for a in list[:q+1]:
        list1.append(a)
    list1.append(99999999999)

    for b in list[q+1:]:
        list2.append(b)
    list2.append(9999999999999999999999999)
    for k in range(len(list)):
        if list1[i]<list2[j]:
            list3.insert(k,list1[i])
            i=i+1
        else:
            list3.insert(k,list2[j])
            j=j+1
    return list3




def mergesort(list,p,r):

    if p<r:

      q=(p+r)/2
      mergesort(list,p,q)
      mergesort(list,q+1,r)
      list = merge(list,p,q,r)
      return list

list=[1,5,7,8,2,4,6,9]

list = mergesort(list,0,7)

print list

合并排序递归错误

Mergesort recursion error

python

mergesort