为什么我的 python 合并排序不起作用？

Question

你能看看下面的代码并帮助我理解为什么我的合并排序代码不起作用吗？我对这段代码做了很多更改，我尝试尽可能地从索引中添加 +1 和删除 -1，但我无法调试它。

#!/usr/bin/python
def Merge(a,p,q,r):
    n1=q-p+1
    n2=r-q
    (l,ri)=([],[])
    for i in range(n1):
        l.append(a[p+i])
    for j in range(1,n2+1):
        ri.append(a[q+j])
    l.append(float('inf'))
    ri.append(float('inf'))
    print 'l and ri are %s and %s' % (l,ri)
    i=0
    j=0
    for k in range(p,r+1):
        if l[i]<=ri[j]:
            a[k]=l[i]
            i+=1
        else:
            a[k]=ri[j]
            j+=1
    print 'a after merge is %s' % (a)

def MergeSort(a,p,r):
#print 'a,P and r are %s, %d and %d' % (a,p,r)
    if p+1<r:
        q=divide(r-p)
        MergeSort(a,p,q)
        print 'After MS of %d and %d' % (p,q)
        MergeSort(a,q+1,r)
        print 'After 2nd MS of %d and %d' % (q+1,r)
        print 'Before Mer of %d and %d and %d' % (p,q,r)
        Merge(a,p,q,r)

def divide(number):
    Q,R=divmod(number,2)
    return Q+int(bool(R))

if __name__=="__main__":
    a=[2,9,6,5,4]
    MergeSort(a,0,len(a)-1)
    print a

是否因为我的数组以 0 索引开头？

Answer 1

This code should be working.

虽然我通常不支持调试解决方案，但您的解决方案存在很多问题。我相信您最好在 Code Review StackExchange site 上分享您的代码以获得更多有用的评论和实践。

我在您的代码中发现的问题大致如下：

糟糕的指数表现。您同时使用了闭合区间和半开区间。如果您能花一些时间来提高对此的理解，您就不会犯那么多不对一的错误或修复。
没有空格 - 您的代码简直不可读。虽然为了清楚起见我没有花太多时间对其进行编辑，但您可以清楚地看到我所做的更改以使其更具可读性。
其他小错误，表明对归并排序算法或编程语言的理解不足 - 例如行 q=divide(r-p)。如果 p = 8 和 r = 10，那么您将得到 q = divide(2)，即 1。因此，您将调用 MergeSort(a, 8, 1) 和 MergeSort(a, 2, 10) - 这是非常错误的。
命名约定，您可以通过使用有意义的变量名来帮助自己。这将显着缩短调试时间。

希望对您有所帮助！

为什么我的 python 合并排序不起作用？

Why is my python merge sort not working?

python

algorithm

sorting

merge

mergesort