这是归并排序的代码。代码运行良好,可以对数字进行排序。但是,如果我们处理必须排序的更大数据,就会出现问题。要排序的数据包含不重复的数字。但是在排序之后,有些数字会重复很多次。我不明白为什么会这样。当我给出一个包含 100000 个数字的数据集时,就会发生这种情况。当要对较小的数据进行排序时,代码工作得很好。
def mergeSort(alist):
if len(alist)>1:
mid = len(alist)/2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i<len(lefthalf) and j<len(righthalf):
if lefthalf[i]<righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i<len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j<len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("select the file: ")
file_name = tkFileDialog.askopenfile(mode='r', title='Select word list file')
inv_data = np.loadtxt(file_name,dtype='float', comments='#', delimiter=None, converters=None, skiprows=0, usecols=None,
unpack=False, ndmin=0)
mergeSort(inv_data)
print("sorted list :", inv_data)
数据集在下面链接http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt
最佳答案
我猜你在发现代码运行良好时使用 Python 列表进行了测试。现在您将它与 NumPy 数组一起使用。关键区别在于像这里那样对 NumPy 数组进行切片
lefthalf = alist[:mid]
righthalf = alist[mid:]
在原始数组上创建 View ,而切片列表创建副本。
当您的算法通过合并 lefthalf
和 righthalf
覆盖 alist
时,所有三个列表必须分开;否则它可能会覆盖尚未合并的项目 lefthalf
。
该错误可以由一个小数组触发:
>>> l = np.arange(10,0,-1)
>>> l
array([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
>>> mergeSort(l)
>>> l
array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
关于python - 这个合并排序 python 代码有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23493805/