python-3.x – 使用Python进行Mergesort

发布时间：2020-12-20 10:32:57 所属栏目：Python 来源：网络整理

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

我找不到任何有效的 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.底层调用从x读取它们的值并直接写入结果.

这样你可以避免所有弹出和追加,这应该可以提高性能.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!