一日一技：如何更好地理解归并排序？

摄影：产品经理

厨师：kingname

请确保你已经看了我昨天的公众号文章。昨天的内容是今天的基础。

一日一技：在 Python 里面如何合并多个有序列表并使得结果依然有序？

在昨天的文章里面，我们已经知道，可以使用 heapq.merge把两个有序列表合并成新的有序列表。

现在，我们来设计一个排序算法，对列表：[1,4,2,0,4,5,1,-3,-8,188,34] 进行排序。

我们现在先把列表拆分成a列表：[1,4,2,0,4,5]和b列表 [1,-3,-8,188,34]。如果我们能够分别让这两个列表各自有序，然后应用昨天的方法，合并一下，最终结果自然就出来了。

那么如何让这两个列表各自有序呢？我们以 [1,4,2,0,4,5]为例。继续把它拆分为两个列表 [1,4,2]和 [0,4,5]。只要这两个列表各自有序，那么合并一下就行了。

我们再来看 [1,4,2]，如何让它有序呢？我们继续分成两个列表 [1]和 [4,2]。显然只有一个元素的列表 [1]是有序的。

再来看 [4,2]，继续分成两个列表 [4]和 [2]。这两个列表都只有一个元素，所以他们都是有序的。此时对他们进行合并，得到 [2,4]。

[1] 与 [2,4]合并，得到 [1,2,4]。

[1,2,4]与 [0,4,5]合并，得到 [0,1,2,4,4,5]。

[0,1,2,4,4,5]与 [-8,-3,1,34,188]合并，得到 [-8,-3,0,1,1,2,4,4,5,34,188]。

排序完成。

整个过程先拆分再合并，这种排序算法叫做 归并算法。它的时间复杂度始终是 O(nlogn)。而我们常常听说的快速排序，只有在最好的情况下时间复杂度才能达到 O(nlogn)。所以归并排序在时间复杂度这个角度是优于快速排序的。

那么如何使用代码来实现呢？合并的部分请看昨天的文章，今天我们主要描述拆分的逻辑：

import heapq

def sort(target):
    if not target:
        return []
    if len(target) == 1:
        return target
    left = target[:len(target) // 2]
    right = target[len(target)//2 :]
    sorted_left = sort(left)
    sorted_right = sort(right)
    result = heapq.merge(sorted_left, sorted_right)
    return result

运行效果如下图所示：

未闻Code

PYTHON干货日更