用Python计算大整数数组中的逆序对

Question

我在用Python写一个程序来计算数组中的逆序对，使用的是Python 2.7。我采用了分治法的算法（也就是归并排序的技巧）。我的程序在处理最多100个元素的数组时运行得很好（这是我能验证的最大值）。

但是，当我用大小为50,000和100,000的数组测试我的程序时，却得不到正确的结果。我把我的代码贴在下面，请大家帮我看看有没有可能的错误：

    f=open('forum.txt')
    a=[]
    s=1
    for line in f:
        a.append(line)





def CountInversion(IntegerArray):
_count=0
lc=0
rc=0
RightArray=[]
LeftArray=[]
if len(IntegerArray)>1:
        LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2])
        RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:])
elif len(IntegerArray)==1:
    return IntegerArray,0
ResultArray=IntegerArray
i=0
l=len(ResultArray)
j,k=0,0
for i in range(0,l):
    if j<len(RightArray) and k<len(LeftArray):
        if RightArray[j]<LeftArray[k]:
            ResultArray[i]=RightArray[j]
            j += 1
            a=(len(LeftArray)-k)
            _count = _count + a    
        else:
            ResultArray[i]=LeftArray[k]
            k += 1
elif j<len(RightArray):
    ResultArray[i]=RightArray[j]
        j += 1
elif k<len(LeftArray):
        ResultArray[i]=LeftArray[k]
        k += 1          
return ResultArray,(_count+lc+rc)

arr,b=CountInversion(a)

print ('end of inversions')

print b

我还运行了J.F. Sebastian在这个帖子中给出的代码，但结果也是一样（对于小输入的答案是正确的，但对于大小为50,000或100,000的输入数组却不对）。

Answer 1

这个问题的解决方法是把字符串转换成整数，然后把这些整数放进数组里。

Answer 2

你的第一个问题是缩进不一致。在某些行上，你使用了制表符（Tab），而不是空格，这样做是非常不好的。因为在Python中，缩进是很重要的，如果不注意，很容易出错。

第二个问题是，你在比较字符串，而不是数字。Python可以很好的对字符串进行排序，但它是按照字典顺序来排序的，这在处理作为字符串编码的整数时可能会让人感到意外。举个例子，字符串"11"会排在字符串"2"前面，因为它的第一个字符1在ASCII字符集中（以及Unicode中）排在2之前。

正如我在评论中提到的，不太清楚你是怎么判断你的代码没有正确工作的。也许只要修复我上面提到的问题，就能解决你遇到的麻烦。如果这些问题没有解决，请解释一下你是怎么判断你的结果是无效的，我会尽量更新这个帖子，给出更多的建议。