我的实现是这样写的:
def merge_sort(lst):
if len(lst) < 2: return lst
midx = len(lst) // 2
return merge(
merge_sort(lst[:midx]),
merge_sort(lst[midx:])
)
def merge(left, right):
merged_lst = []
while left and right:
merged_lst.append((left.pop(0) if left[0] <= right[0] else right.pop(0)))
merged_lst.extend(left if left else right)
return merged_lst
然后我在网上找到了这个:
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
我原以为我的会更快,但会占用更多内存。然后我分析了 med_lst
和 big_lst
:
med_lst = [random.random() for _ in range(100000)]
big_lst = [random.random() for _ in range(500000)]
在 Jupyter notebook 中使用这样结构的代码:
printmd(f'RAM at start: {memory_profiler.memory_usage()[0]:0.1f}MiB', color='blue')
t1 = time.time()
printmd(f'Sorting: {len(big_lst)} elements', color="blue")
merge_sort(big_lst)
t2 = time.time()
printmd(f'RAM after sorting list: {memory_profiler.memory_usage()[0]:0.1f}MiB, took {t2 - t1:0.1f}s', color='blue')
时间复杂度让我吃惊:
中等列表:
merge_sort
:1.2s
合并排序
:0.6s
大名单:
merge_sort
:29.0s
mergeSort
:3.4s
这是否意味着只是因为创建了一个新列表,并且可能发生了冲突或调整了大小?还是我的实现/思考过程有误(菜鸟错误——这个答案得 0 分)?我认为我的函数仍然是 0(nlogn)
,但是随着集合变大,您真的可以说它们是“可比较的”吗
我没有逐行分析这一点,因为它更基础
最佳答案
正如@CH 在评论中指出的,前面的 pop()
是罪魁祸首。
通过在弹出之前反转列表然后在弹出之后反转,我设法使我的实现实际上比另一个更快:
def merge(left, right):
merged_lst = []
if left: left.reverse()
if right: right.reverse()
while left and right:
merged_lst.append((left.pop() if left[-1] <= right[-1] else right.pop()))
if left: left.reverse()
if right: right.reverse()
merged_lst.extend(left if left else right)
return merged_lst
中等列表:merge_sort
:0.5s mergeSort
:0.7s
大列表:merge_sort
:2.6s mergeSort
:4.0s
关于python - 解释了两种不同合并排序实现之间的比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65347802/