为什么我的Python中的归并排序这么慢？

3 投票

4 回答

5338 浏览

提问于 2025-04-16 23:36

我对这个行为有点困惑。
我用timeit模块来测量执行时间，结果显示在10000次循环中：

归并排序（Merge）: 1.22722930395
冒泡排序（Bubble）: 0.810706578175
选择排序（Select）: 0.469924766812

这是我写的归并排序代码：

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

编辑：

我把列表操作改成了使用指针，现在我的测试用的是1000个从0到1000的随机数字。（顺便说一下：我这里只进行了10次循环）

结果：

归并排序（Merge）: 0.0574434420723
冒泡排序（Bubble）: 1.74780097558
选择排序（Select）: 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

现在似乎运行得很好 :)

列表操作时间复杂度排序算法性能测试随机数生成冒泡排序归并排序选择排序

4 个回答

你的归并排序有一个很大的常数因素，只有在处理大列表时，你才能看到它在复杂度上的优势。

回答于 2025-04-16 由 Python大师

分享举报

list.pop(0) 这个操作会把列表中的第一个元素拿掉，但为了做到这一点，后面的所有元素都得往前挪，这样就会多花费一些时间，具体来说是O(n)的时间复杂度，这样的操作最好避免。

另外，切片一个list对象会创建一个新的副本：

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

这意味着你会使用O(n * log(n))的内存，而不是O(n)的内存。

我看不到冒泡排序的具体实现，但我敢肯定它是原地排序的，所以它运行得更快也就不奇怪了。

你需要把它改写成原地排序。与其复制原始列表的一部分，不如传递起始和结束的索引。

回答于 2025-04-16 由 Python大师

分享举报

首先，我想说的是：我无法重现你在100次循环和大小为10000的列表上得到的时间结果。 这里有一个关于所有实现的详细基准测试，包括冒泡排序和你原来的代码，结果可以在这个链接这里找到。我发现单次运行的平均时间如下：

Python自带的(Tim)排序：0.0144600081444
冒泡排序：26.9620819092
（你的）原始归并排序：0.224888720512

现在，要让你的函数更快，你可以做几件事。

编辑：显然，我之前说错了（感谢 cwillu）。在Python中，计算长度是O(1)。不过，去掉一些无用的计算还是能稍微提高性能（原始归并排序：0.224888720512，无长度归并排序：0.195795390606）：

def nolenmerge(array1,array2):
    merged_array=[]
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop(0))
        elif (not array2) or array1[0] < array2[0]:
            merged_array.append(array1.pop(0))
        else:
            merged_array.append(array2.pop(0))
    return merged_array

def nolenmergeSort(array):
    n  = len(array)
    if n <= 1:
        return array
    left = array[:n/2]
    right = array[n/2:]
    return nolenmerge(nolenmergeSort(left),nolenmergeSort(right))

第二，正如这个回答所建议的，pop(0)是线性的。把你的合并操作改成在最后使用pop()：

def fastmerge(array1,array2):
    merged_array=[]
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
        else:
            merged_array.append(array2.pop())
    merged_array.reverse()
    return merged_array

这样做又快了一些：无长度归并排序：0.195795390606，无长度归并排序+快速合并：0.126505711079

第三 - 这只有在你使用支持尾调用优化的语言时才有用，如果没有，这个做法是一个坏主意 - 你对merge的调用不是尾递归; 它在调用(merge)时同时递归调用了(mergeSort left)和(mergeSort right)，而此时还有剩余的工作。

但是你可以通过使用CPS来使合并变成尾递归（如果不进行尾调用优化，处理稍微大的列表时会导致栈溢出）：
```
def cps_merge_sort(array):
    return cpsmergeSort(array,lambda x:x)

def cpsmergeSort(array,continuation):
    n  = len(array)
    if n <= 1:
        return continuation(array)
    left = array[:n/2]
    right = array[n/2:]
    return cpsmergeSort (left, lambda leftR:
                         cpsmergeSort(right, lambda rightR:
                                      continuation(fastmerge(leftR,rightR))))
```
完成这个后，你可以手动进行尾调用优化，把递归调用的栈管理转移到普通函数的循环中（跳板技术，例如在这里有解释，这个技巧最初是由Guy Steele提出的）。跳板技术和CPS结合得很好。

你写一个“延迟执行”的函数，它“记录”并延迟应用：它接受一个函数和它的参数，返回一个函数，这个函数在调用时会返回（原始函数应用于这些参数的结果）。
```
thunk = lambda name, *args: lambda: name(*args)
```
然后你写一个跳板，管理对延迟执行函数的调用：它会一直调用延迟执行函数，直到返回一个结果（而不是另一个延迟执行函数）
```
def trampoline(bouncer):
    while callable(bouncer):
        bouncer = bouncer()
    return bouncer
```
最后，只需“冻结”（延迟执行）你原始CPS函数中的所有递归调用，让跳板按正确的顺序解开它们。你的函数现在在每次调用时返回一个延迟执行的函数，而不使用递归（并且不保留自己的栈帧）：
```
def tco_cpsmergeSort(array,continuation):
    n  = len(array)
    if n <= 1:
        return continuation(array)
    left = array[:n/2]
    right = array[n/2:]
    return thunk (tco_cpsmergeSort, left, lambda leftR:
                  thunk (tco_cpsmergeSort, right, lambda rightR:
                         (continuation(fastmerge(leftR,rightR)))))

mycpomergesort = lambda l: trampoline(tco_cpsmergeSort(l,lambda x:x))
```

可惜这样做并没有那么快（递归归并排序：0.126505711079，这个跳板版本：0.170638551712）。好吧，我想递归归并排序算法的栈增长其实是适度的：一旦你走出数组切片递归模式的最左路径，算法就开始返回（并移除栈帧）。所以对于大小为10K的列表，你的函数栈最多只有log_2(10 000) = 14……这算是相当适度。

你可以做稍微复杂一点的基于栈的尾调用优化，如这个SO回答所示：

    def leftcomb(l):
        maxn,leftcomb = len(l),[]
        n = maxn/2
        while maxn > 1:
            leftcomb.append((l[n:maxn],False))
            maxn,n = n,n/2
        return l[:maxn],leftcomb

    def tcomergesort(l):
        l,stack = leftcomb(l)
        while stack: # l sorted, stack contains tagged slices
            i,ordered = stack.pop()
            if ordered:
                l = fastmerge(l,i)
            else:
                stack.append((l,True)) # store return call
                rsub,ssub = leftcomb(i)
                stack.extend(ssub) #recurse
                l = rsub
        return l

但是这也只是稍微快一点（跳板归并排序：0.170638551712，这个基于栈的版本：0.144994809628）。显然，Python在我们原始归并排序的递归调用中构建栈的开销是相当小的。

最终结果呢？在我的机器上（Ubuntu natty的标准Python 2.7.1+），在100次运行（除了冒泡排序）中，大小为10000的列表（包含0到10000000的随机整数）的平均运行时间如下：

Python自带的(Tim)排序：0.0144600081444
冒泡排序：26.9620819092
原始归并排序：0.224888720512
无长度归并排序：0.195795390606
无长度归并排序 + 快速合并：0.126505711079
跳板CPS归并排序 + 快速合并：0.170638551712
基于栈的归并排序 + 快速合并：0.144994809628

回答于 2025-04-16 由 Python大师

分享举报

为什么我的Python中的归并排序这么慢？

编辑：

4 个回答

撰写回答