问题描述
我正在尝试使用 Python 计算长文本文件中的反转次数。
我不断收到left = sortCount(alist, len1, i)行上的错误
import csv
def mergeCount(alist, i, len1, len2):
print("Merge")
inv = 0
temp = []
index1 = i
index2 = i + len1
while index1 < i + len1 and index2 < i + len1 + len2:
if alist[index1] <= alist[index2]:
temp.append(alist[index1])
index1 += 1
else:
temp.append(alist[index2])
index2 += 1
inv += i + len1 - index1
if index2 == i + len1 + len2:
temp.extend(alist[index1 : i + len1])
else:
pass
write = i
for value in temp:
alist[write] = value
write += 1
return inv
def sortCount(alist, n, i=0):
#print("Sort")
if len(alist) <= 1:
return 0
else:
len1 = n // 2
len2 = n // 2 + n % 2
left = sortCount(alist, len1, i)
right = sortCount(alist, len2, i + len1)
mergeInv = mergeCount(alist, i, len1, len2)
return left + right + mergeInv
def safeint(val):
try:
return int(val)
except ValueError:
return val
alist = []
with open('IntegerArray.txt') as f:
lines = csv.reader(f, delimiter='\n')
for line in lines:
line = map(safeint, line)
alist.append(line)
print sortCount(alist, len(alist), 0)
1楼
当len1变为zero ，您会不断地一次又一次地调用left = sortCount(alist, 0, i)同样的事情。
如果len1==0返回0
if len1==0:
return 0
left = sortCount(alist, len1, i)
right = sortCount(alist, len2, i + len1)
像下面这样修改你的sortCount ：
def sortCount(alist, n, i=0):
if len(alist) <= 1:
return 0
else:
len1 = n // 2
len2 = n // 2 + n % 2
if len1==0:
return 0
left = sortCount(alist, len1, i)
right = sortCount(alist, len2, i + len1)
mergeInv = mergeCount(alist, i, len1, len2)
return left + right + mergeInv