我找不到任何有效的Python 3.3 mergesort算法代码,所以我自己做了一个。有什么办法可以加快速度吗?它在约0.3-0.5秒内对20,000个数字进行排序
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的顶级调用中初始化整个结果列表:
result = [0]*len(x) # replace 0 with a suitable default element if necessary. # or just copy x (result = x[:])
然后,对于递归调用,您可以使用一个辅助函数,该函数不会将子列表传递给,而是将其传递给x。底层调用从中读取值x并result直接写入。
x
result
这样,你能避免所有的pop荷兰国际集团和append荷兰国际集团应该提高性能。
pop
append