我找不到任何可用的 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.
更多推荐
使用 Python 进行归并排序
发布评论