问题描述
我正在尝试使用合并排序算法来计算包含1到100,000范围内所有数字的数组中的反转。 当我输入一个小数据集但在输入包含较大数组的文件时没有返回正确的答案时,它工作正常。 可能是我输入文件的方式有问题吗? 我以前从来没有把文件输入到数组中,所以我不能肯定地说我是否正确地做了。
file = open('IntegerArray.txt','r')
integerArray = []
for line in file:
integerArray.append(line)
inversions = 0
def divide(list):
if len(list) > 1:
middle = int(len(list) / 2)
left = divide(list[:middle])
right = divide(list[middle:])
#left = divide(left)
#right = divide(right)
elif len(list) <= 1:
return list
return merge(left,right)
def merge(left,right):
global inversions
result = []
while left != [] and right != []:
if left[0] < right[0]:
result.append(left[0])
if len(left) > 1:
left = left[1:]
else:
left = []
elif left[0] > right[0]:
result.append(right[0])
inversions += len(left)
if len(right) > 1:
right = right[1:]
else:
right = []
if left != []:
result += left
if right != []:
result += right
return result
divide(integerArray)
print(inversions)
这应返回2407905288,但返回2397819672。
1楼
似乎它不适用于数字大于9的大多数情况! 您将数字保存在字符串列表中。 所以合并函数中的比较器比较两个字符串,所以例如2大于12!
至少你需要改变你的第一行:
file = open('IntegerArray.txt','r')
integerArray = []
for line in file.readlines():
integerArray.append(int(line.strip()))
2楼
尝试k方式合并排序 。 大数据集的问题是简单的合并排序必须在运行时将两个大型数组带入主内存,这有时是不可能的。