我正在实现一个带反转计数的合并排序。 我的代码可以很好地处理我的小输入文件(10个元素),但是当它达到100000时, 它似乎从brute search返回了不正确的答案。有时更大,有时更小。有人知道吗?在
我的代码返回2402298631。 输入文件位置 http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt
def msort_inv2(m):
global count
if len(m) <= 1:
return m
result = []
middle = int(len(m)/2)
left = msort_inv2(m[:middle])
right = msort_inv2(m[middle:])
while (len(left) > 0) or (len(right) > 0):
if (len(left) > 0) and (len(right) > 0):
if left[0] > right[0]:
result.append(right[0])
count = count + len(left)
right.pop(0)
else:
result.append(left[0])
left.pop(0)
elif len(right) > 0:
for i in right:
result.append(i)
right.pop(0)
else:
for i in left:
result.append(i)
left.pop(0)
return result
错误存在于以下部分
修正应该是这样的
^{pr2}$数组中的for循环同时弹出项,会导致python中的奇怪行为。在
相关问题 更多 >
编程相关推荐