使用 Python 进行归并排序

Question

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

原文由 Hans 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

然后对于递归调用，您可以使用辅助函数，您传递的不是子列表，而是 x 的索引。底层调用从 x 读取它们的值并直接写入 result 。

这样你就可以避免所有 pop ing 和 append ing 应该提高性能。

原文由 firefrorefiddle 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

第一个改进是简化主循环中的三种情况：与其在某些序列有元素时进行迭代，不如在 两个 序列都有元素时进行迭代。离开循环时，其中一个将为空，我们不知道是哪个，但我们不关心：我们将它们附加在结果的末尾。

 def msort2(x):
    if len(x) < 2:
        return x
    result = []          # moved!
    mid = int(len(x) / 2)
    y = msort2(x[:mid])
    z = msort2(x[mid:])
    while (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)
    result += y
    result += z
    return result

第二个优化是避免 pop ping 元素。相反，有两个指数：

 def msort3(x):
    if len(x) < 2:
        return x
    result = []
    mid = int(len(x) / 2)
    y = msort3(x[:mid])
    z = msort3(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

最后的改进在于使用非递归算法对短序列进行排序。在这种情况下，我使用内置的 sorted 函数并在输入大小小于 20 时使用它：

 def msort4(x):
    if len(x) < 20:
        return sorted(x)
    result = []
    mid = int(len(x) / 2)
    y = msort4(x[:mid])
    z = msort4(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

我对 100000 个整数的随机列表进行排序的测量结果是原始版本为 2.46 秒，msort2 为 2.33，msort3 为 0.60，msort4 为 0.40。作为参考，使用 sorted 对所有列表进行排序需要 0.03 秒。

原文由 anumi 发布，翻译遵循 CC BY-SA 4.0 许可协议