使用 Python 进行归并排序 [英] Mergesort with Python
问题描述
我找不到任何可用的 Python 3.3 归并排序算法代码,所以我自己做了一个.有什么办法可以加快速度吗?它在大约 0.3-0.5 秒内对 20,000 个数字进行排序
I couldn't find any working Python 3.3 mergesort algorithm codes, so I made one myself. Is there any way to speed it up? It sorts 20,000 numbers in about 0.3-0.5 seconds
def msort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2)
y = msort(x[:mid])
z = msort(x[mid:])
while (len(y) > 0) or (len(z) > 0):
if len(y) > 0 and len(z) > 0:
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
elif len(z) > 0:
for i in z:
result.append(i)
z.pop(0)
else:
for i in y:
result.append(i)
y.pop(0)
return result
推荐答案
你可以在对mergesort的顶级调用中初始化整个结果列表:
You can initialise the whole result list in the top level call to mergesort:
result = [0]*len(x) # replace 0 with a suitable default element if necessary.
# or just copy x (result = x[:])
然后,对于递归调用,您可以使用辅助函数,您不是将子列表传递给它,而是将索引传递给 x
.底层调用从 x
读取它们的值并直接写入 result
.
Then for the recursive calls you can use a helper function to which you pass not sublists, but indices into x
. And the bottom level calls read their values from x
and write into result
directly.
这样你就可以避免所有应该提高性能的 pop
ing 和 append
ing.
That way you can avoid all that pop
ing and append
ing which should improve performance.
这篇关于使用 Python 进行归并排序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!