使用 Python 进行归并排序

本文介绍了使用 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.

这样你就可以避免所有应该提高性能的 poping 和 appending.

That way you can avoid all that poping and appending which should improve performance.