Python合并算法

Question

这似乎现在有效...欢迎公开批评。 Ty tsroten。

debug = 1
#List to be merged
A=[1,2,3,4,5,6,1,2,3,4,5,6,7]

#Artificial variables from calling function
p=0
r=len(A)
q=int(((p+r)/2)-1)

#List to append merged values
B=[]

#End of list
end=len(A)

if debug:
    print ('Mid: %d\n' % (q))
    print ('End: %d' % (end))

#Left and Right lists with sentinels
L=A[:q+1]
R=A[q+1:]
L.append(None)
R.append(None)

#Init counters
i=k=j=l=0

if debug:
    print ('A:%s' %(A))
    print ('\n')
    print ('L:%s' %(L))
    print ('R:%s' %(R))
    print ('\n')

#Merge Left and Right lists
for k in A:
    if debug:
        print ('Iteration:%d' % (l))
        l+=1
        print ('i=%d, j=%d' % (i, j))
        print ('B:%s' %(B))
        print ('\n')
    if L[i] is not None and L[i]<=R[j]:
        B.append(L[i])
        i+=1
    else:
        B.append(R[j])
        j+=1

print ('Result:',B)

我正在尝试用 Python 编写合并算法，但我一直遇到这个错误。

Traceback (most recent call last):
  File "C:/Python34/Scripts/mergeSort.py", line 19, in <module>
    if L[i]<=R[j] and i<mid:
IndexError: list index out of range

我看过其他算法，但它们似乎没有同样的问题。请帮忙。

A=[2,4,5,7,1,3,7,8,9]  
B=[]


end=len(A)  
mid=int(end/2)

L=A[:mid]  
R=A[mid+1:]

i=k=j=0

for k in A:  
    if L[i]<=R[j] and i<mid:  
        B.append(L[i])  
        i+=1  
    elif j<end:  
        B.append(R[j])  
        j+=1  

print (B)

Answer 1

您的 for 循环遍历 A 中的所有项目，它比 L 或 R 长。因此，在某些时候，i 和 j 变得大于 L 和 R 的长度。此时，引用 L[i] 或 R[j] 会引发 IndexError。