使用Python的Mergesort

问题描述

我找不到任何有效的Python 3.3 mergesort算法代码，所以我自己做了一个.有什么办法可以加快速度吗?它可以在约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.

这样，您就可以避免所有应该改善性能的pop和append ing.

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

这篇关于使用Python的Mergesort的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！