python - 为什么我的 MergeSort 在 Python 中这么慢？

Question

我在理解这种行为时遇到了一些麻烦。我正在使用 timeit 模块测量执行时间并获得以下 10000 周期的结果:

• 合并:1.22722930395
• 气泡:0.810706578175
• 选择:0.469924766812

这是我的 MergeSort 代码:

def mergeSort(array):
    if len(array) <= 1:
        return array
    else:
        left = array[:len(array)/2]
        right = array[len(array)/2:]
        return merge(mergeSort(left),mergeSort(right))

def merge(array1,array2):
    merged_array=[]
    while len(array1) > 0 or len(array2) > 0:

        if array2 and not array1:
            merged_array.append(array2.pop(0))

        elif (array1 and not array2) or array1[0] < array2[0]:
            merged_array.append(array1.pop(0))

        else:
            merged_array.append(array2.pop(0))
    return merged_array

编辑:

我已将列表操作更改为使用指针，我的测试现在可以使用 0-1000 之间的 1000 个随机数的列表。 (顺便说一句:我在这里改为只有 10 个周期)

结果:

• 合并:0.0574434420723
• 气泡:1.74780097558
• 选择:0.362952293025

这是我重写的合并定义:

def merge(array1, array2):
    merged_array = []
    pointer1, pointer2 = 0, 0
    while pointer1 < len(array1) and pointer2 < len(array2):
        if array1[pointer1] < array2[pointer2]:
            merged_array.append(array1[pointer1])
            pointer1 += 1
        else:
            merged_array.append(array2[pointer2])
            pointer2 += 1
    while pointer1 < len(array1):
        merged_array.append(array1[pointer1])
        pointer1 += 1

    while pointer2 < len(array2):
        merged_array.append(array2[pointer2])
        pointer2 += 1

    return merged_array

现在看起来工作得很好 :)

Answer 1

list.pop(0) 弹出第一个元素并且必须移动所有剩余的元素，这是一个额外的 O(n) 操作，不能发生。

此外，切片 list 对象会创建一个副本:

left = array[:len(array)/2]
right = array[len(array)/2:]

这意味着您还使用了 O(n * log(n)) 内存而不是 O(n)。

我看不到 BubbleSort，但我敢打赌它就地工作，难怪它更快。

您需要重写它才能就地工作。不是复制原始列表的一部分，而是传递开始和结束索引。