一尘不染

与Python合并

algorithm

我找不到任何有效的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

阅读 247

收藏
2020-07-28

共1个答案

一尘不染

您可以在对mergesort的顶级调用中初始化整个结果列表:

result = [0]*len(x)   # replace 0 with a suitable default element if necessary. 
                      # or just copy x (result = x[:])

然后,对于递归调用,您可以使用一个辅助函数,该函数不会将子列表传递给,而是将其传递给x。底层调用从中读取值xresult直接写入。

这样,你能避免所有的pop荷兰国际集团和append荷兰国际集团应该提高性能。

2020-07-28