我的合并排序实现有问题,因为在调用合并之前我没有得到两个排序列表。我不确定它有什么问题。
def mergeSort(arr):
if len(arr) == 1 : return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
mergeSort(left_half)
mergeSort(right_half)
return merge(left_half,right_half)
def merge(list1,list2):
res = []
i = 0
j = 0
while i < len(list1) and j < len(list2):
if list1[i] < list2[j]:
res.append(list1[i])
i += 1
elif list1[i] > list2[j]:
res.append(list2[j])
j += 1
#Add remaining to res if any
while i < len(list1):
res.append(list1[i])
i += 1
while j < len(list2):
res.append(list2[j])
j += 1
return res
A = [5,1,2,15]
print(mergeSort(A))
我对合并排序的理解是空间复杂度是 O(n),因为内存中有 n 个项目(在最终合并中)。快速排序是否优于合并排序只是因为快速排序就地?
最佳答案
我不是python专家,但你应该写
left_half = arr[:mid]
right_half = arr[mid:]
left_half = mergeSort(left_half)
right_half = mergeSort(right_half)
因为您的 mergeSort 返回已排序数组的副本。
关于python-3.x - 错误的合并排序实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52572185/