Algorithms Part 1-Question 1- the number of inversions-逆序数计算算法

def countInversion(arrayList):
    if len(arrayList)==1:
        return (0,arrayList)
    
    halfIndex=int(len(arrayList)/2.0)
    countA,sortedA=countInversion(arrayList[:halfIndex])
    countB,sortedB=countInversion(arrayList[halfIndex:])
    returnList=[]
    i=0
    j=0
    countInter=0
    
    for index in range(0,len(arrayList)):
        if i<len(sortedA) and j<len(sortedB):
            if sortedA[i]<sortedB[j]:
                returnList.append(sortedA[i])
                i+=1
            else:
                returnList.append(sortedB[j])
                j+=1
                countInter+=len(sortedA)-i
        elif i<len(sortedA):
            returnList.append(sortedA[i])
            i+=1
        elif j<len(sortedB):
            returnList.append(sortedB[j])
            j+=1
            
    return (countA+countB+countInter,returnList)

f=open('IntegerArray.txt','r')
listAll=[]
for line in f.readlines():
    listAll.append(int(line))
f.close()

print listAll
countAll,sortedAll=countInversion(listAll)
print countAll#,sortedAll

合并两个子list计算inversions的时候，要注意是加上sortedA所有剩下的元素数量。

程序在windows下运行十分缓慢，大约20分钟过去还没有运行完毕，但在linux下不过一秒就运行结束。其中的原因有待推敲。