mergesort,递归基本情况和排序问题

2024-03-29 04:46:15 发布

您现在位置:Python中文网/ 问答频道 /正文

我用Python实现了以下Mergesort算法:

def mergeSort(listNumbers,ini,end):
    if ini==end:
        return listNumbers
    else:
        mid=(ini+end)/2
        mergeSort(listNumbers,ini,mid)
        mergeSort(listNumbers,mid+1,end)
        merge(listNumbers,ini,mid,end)

def merge(listNumbersT,ini,mid,end):
    b=[]
    ind1=ini
    ind2=mid+1
    while ind1<=mid and ind2<=end:
        if listNumbersT[ind1]<listNumbersT[ind2]:
            b.append(listNumbersT[ind1])
            ind1=ind1+1
        else:
            b.append(listNumbersT[ind2])
            ind2=ind2+1
    while ind1<=mid:
        b.append(listNumbersT[ind1])
        ind1=ind1+1
    while ind2<=end:
        b.append(listNumbersT[ind2])
        ind2=ind2+1
    listNumbersT=b
    print listNumbersT

def main():
    l=[4,1,8,2,5,9,10]
    print mergeSort(l,0,len(l)-1)

if __name__=="__main__":
    main()

我不知道如何修复我对mergeSort的递归调用的基本情况,当我运行程序时,它不会打印任何结果;我必须打印最终结果的唯一方法是添加:

打印列表编号

在merge函数中,如何修复此问题?而且它似乎没有排序我的列表的最后一个元素。你知道吗

有什么帮助吗?你知道吗

谢谢


Tags: ifmaindefmergeelseiniendmid
2条回答

我把你的分类放在适当的地方,这样做就行了。在某些地方,你返回的名单,其他地方没有那么多。你知道吗

修改后的mergeSort函数如下所示:

def mergeSort(listNumbers,ini,end):
    if ini < end:
        mid=(ini+end)/2
        mergeSort(listNumbers,ini,mid)
        mergeSort(listNumbers,mid+1,end)
        merge(listNumbers,ini,mid,end)

这意味着基本情况是ini >= endlistNumbers保持不变。你知道吗

merge函数的末尾,我将listNumbersT = b替换为:

    for i,value in enumerate(b):
        listNumbersT[ini + i] = value

它将b的元素复制回原始的listNumbersT。同样,这使更改“就位”在原始列表上,因此不需要返回任何内容。你知道吗

这使得main

def main():
    l=[4,1,8,2,5,9,10]
    mergeSort(l,0,len(l)-1)   # sort l in-place
    print l                   # [1, 2, 4, 5, 8, 9, 10]

一个小的调整-将mergeSort函数的开头改为

def mergeSort(listNumbers,ini=0,end=-1):
    if end < 0:
        end += len(listNumbers)

main中的调用变得很简单:

mergeSort(l)

对于用户来说,这稍微容易一些。你知道吗

不需要太多修改代码

在函数merge中,listNumbersT=b行重新分配变量listNumbersT,因此丢失了那里的值,破坏了递归。你知道吗

要解决这个问题,请用下面的循环替换函数merge中的listNumbersT=b。你知道吗

for i,number in enumerate(b):
    listNumbersT[ini + i] = number

要获得正确的返回值,您需要在mergeSort函数的末尾有一个返回值,例如

def mergeSort(listNumbers,ini,end):
    if ini==end:
        return listNumbers
    else:
        mid=(ini+end)/2
        mergeSort(listNumbers,ini,mid)
        mergeSort(listNumbers,mid+1,end)
        merge(listNumbers,ini,mid,end)

    return listNumbers

但是,l将被重新排序,因此您实际上不需要在mergeSort末尾返回。你知道吗

干杯

相关问题 更多 >