排序nlog(n), 2022-06-01

2022-06-01 本文已影响0人 Mc杰夫

(2022.06.01 Wed)
这里介绍三种复杂度为 $nlog(n)$ 的排序算法，并归排序(merge sort)、快速排序(quick sort)和堆排序(heap sort)。

并归排序Merge sort

Divide-and-Conquer分治

Merge sort和quick sort的设计思路是算法设计模式中的Divide-and-conquer(DaC)分治思想，DaC方法分为如下三步：

Divide分：将输入数据拆分为两个或更多个子集(disjoint subsets)，如果输入数据的size小于特定阈值(比如1或2个元素)，则直接解决问题返回结果
Conquer治：以递归方式解决子集相关联的子问题
Combine合：将子问题的解决方案合并(merge)在一起形成初始问题的解决方案

算法描述

对于有 $n$ 个元素的序列 $S$ ，使用merge sort排序的过程如下：

分：如果 $S$ 没有或只有一个元素，直接返回 $S$ ，排序已完成。其他情况下，将 $S$ 分为两个子序列 $S1$ 和 $S2$ ，每个子序列包含 $S$ 的大约一半元素，其中 $S1$ 包含 $S$ 的前 $\lfloor n/2\rfloor$ 项， $S2$ 包含余下的 $\lceil n/2\rceil$ 项
治：递归的方式对子序列 $S1$ 和 $S2$ 排序
合：对于排序完成的 $S1$ 和 $S2$ ，将其中元素根据大小合并到序列 $S$ 中，使其保持sorted状态

下面这张图通过merge-sort tree的形式展示了merge sort的过程。

merge sort demo

复杂度分析

这里按divide-conquer-combine的循序依次分析

divide：在这个阶段，每一步都要将序列 $S$ 拆分成新的两个子序列，也就是原序列中所有元素都将复制到两个新的序列中，不管是从 $n$ 个分解成两个 $n/2$ 序列，还是从 $n/2$ 序列分解成两个 $n/4$ 序列，总的元素个数都是 $n$ ，因此该操作的复杂度为 $O(n)$ 。因每次都对序列做binary split，因此一共执行 $\lceil log(n)\rceil$ 次binary split。因此这部分的复杂度是 $O(nlog(n))$ 。
conquer&combine：在conquer阶段，每一层的所有节点，都要进行比较和写入新序列(combine)的动作，因此执行这两个动作的复杂度是 $O(n)$ 。执行所有 $\lceil log(n) \rceil$ 层之后，总的复杂度为 $O(nlog(n))$ 。

merge sort的运行时间分析

综合上面分析，merge sort的总复杂度为 $O(nlog(n))$ 。

算法实现

(2022.06.02 Thur)

Array-based

首先实现对两个序列的merge操作

def merge(s, s1, s2):
    # non-decreasing order
    i, j = 0, 0
    while i+j < len(s):
        if j == len(s2) or ( i < len(s1) and s1[i] < s2[j]):
            s[i+j] = s1[i]
            i += 1
        else:
            s[i+j] = s2[j]
            j += 1

这里使用了双指针法，对 $s1$ 和 $s2$ 两个序列设置两个指针 $i$ 和 $j$ 。指针对应的序列停止向结果序列写数据的条件是该指针指到了对应序列的结尾，或指针对应的值大于另一个指针对应的值。

另外，需要注意while语句中判断的条件，在(i<len(s1) and s1[i] < s[j])这条语句中，判断指针是否超过s1 index的语句即 $i<len(s1)$ 放在前面，这样可以避免下一步做 $s[i]<s[j]$ 的判断时报index out of range的错误。如果指针超过s1长度，则直接跳过。这里利用了Python的lazy evaluation属性。

下面实现merge sort。

def merge_sort(s):
    # sort with merge method
    n = len(s)
    print('s length: ', n)
    if n < 2:
        return 
    print('enter into the function')
    # divide 
    mid = n//2
    s1 = s[:mid]
    print('s1 length: ', len(s1))
    s2 = s[mid:n]
    print('s2 length: ', len(s2))
    # conquer recursively
    merge_sort(s1)
    merge_sort(s2)
    # combine
    merge(s, s1, s2)

Linked list-based

def merge(s, s1, s2):
    while not s1.is_empty() and not s2.is_empty():
        if s1.first() < s2.first():
            s.enqueue(s1.dequeue())
        else:
            s.enqueue(s2.dequeue())
    while not s1.is_empty():
        s.enqueue(s1.dequeue())
    while not s2.is_empty():
        s.enqueue(s2.dequeue())

def merge(s):
    n = len(s)
    if n < 2:
        return
    # divide
    s1 = LinkedQueue()
    s2 = LinkedQueue()
    while len(s1) < n//2:
        s1.enqueue(s.dequeue())
    while not s.is_empty():
        s2.enqueue(s.dequeue())
    # conquer
    merge(s1)
    merge(s2)
    # combine
    merge_sort(s, s1, s2)

一种自底至上的非递归并归排序方法

该方法不使用递归，基于array，复杂度 $O(nlogn)$ 。相比于递归方法在实践中稍快，因为减少了递归的overhead和对临时内存的使用。基本思路是从底开始，逐层实现merge sort。给定一个数组，从头开始将连续的两个元素排序成一个长度为2的数组，并以此执行，直到整个数组排序完成。

def merge(src, result, start, inc):
    end1 = start + inc
    end2 = min(start + 2*inc, len(src))
    x, y, z = start, start+inc, start 
    while x < end1 and y < end2:
        if src[x] < src[y]:
            result[z] = src[x]; x += 1
        else:
            result[z] = src[y]; y += 1
        z += 1
    if x < end1:
        result[z:end2] = src[x:end1]
    elif y < end2:
        result[z:end2] = src[y:end2]

def merge sort(S):
    '''Sort the elements of Python list S using the merge-sort algorithm.''' 
    n = len(S)
    logn = math.ceil(math.log(n,2))
    src, dest = S, [None] * n
    for i in (2**k for k in range(logn)):
        for j in range(0, n, 2*i): 
            merge(src, dest, j, i)
        src, dest = dest, src 
    if S is not src:
        S[0:n] = src[0:n]

快速排序

(2022.06.15 Wed)
与merge sort相似，快速排序也采用了divide-and-conquer范式。不同的是快速排序在递归之前已经做了一部分排序。

快速排序有多种实现方式，但是算法描述相差不大，表述如下：

分divide：未排序的序列 $S$ 至少有两个元素，选定一个元素 $x$ 作为基准点，称作pivot，通常选 $S$ 中的最后一个元素作为pivot。从 $S$ 中移除所有元素，并将他们分为三个子序列
- $L$ ，保存了 $S$ 中所有比 $x$ 小的元素
- $E$ ，保存了 $S$ 中所有与 $x$ 相同的元素，如果 $S$ 中的元素互不相同，则 $E$ 只有pivot $x$ 本身
- $G$ ，保存了 $S$ 中所有比 $x$ 大的元素
排conquer：以递归的方式对 $L$ 和 $G$ 排序
合combine：将排序完成的 $L$ 和 $G$ 放回序列 $S$ ，顺序是 $L$ - $E$ - $G$ ，排序完成

quick sort schematic

quick sort demo

基于linked list的quick sort实现

该实现方式使用了LinkedQueue这种数据结构。

def quick_sort(S):
    # divide, and initially conquer
    L, G, E = LinkedQueue(), LinkedQueue(), LinkedQueue()
    pivot = S.first()
    while S.empty() is not True:
        if S.first() > pivot:
            G.enqueue(S.dequeue())
        elif S.first() < pivot:
            L.enqueue(S.dequeue())
        else:
            E.enqueue(S.dequeue())
    # conquer with recursion
    quick_sort(L)
    quick_sort(G)
    # combine
    while L.empty() is not True:
        S.enqueue(L.dequeue())
    while E.empty() is not True:
        S.enqueue(E.dequeue())
    while G.empty() is not True:
        S.enqueue(G.dequeue())

快速排序的运行时间分析

通过分析快速排序树上每个节点的运行时间，可以得到算法的运行时间。

在排序节点 $v$ 上的运行时间正比于 $v$ 的 $s(v)$ 的输入大小，也就是与节点 $v$ 关联的快速排序调用的序列尺寸。考虑到子序列 $E$ 至少有一个元素，则 $v$ 的子节点的输入尺寸之和最小为 $s(v)-1$ 。

运行时间复杂度为 $O(n \cdot h)$ ，其中的 $h$ 是快速排序树的总高度。最坏的情况下，该树的高度是 $\Theta(n)$ ，此时的复杂度是 $O(n^2)$ 。一种可能的情况是我们选序列的最后元素作为pivot，而该序列已经完成了从小到大的排序，这时的复杂度最高。

当经过拆分的 $L$ 和 $G$ 尺寸相差不多，或者相等时，快速排序树的高度为 $O(\log n)$ 。可以证明，当 $L$ 和 $G$ 的长度在 $\frac{1}{4} n$ 到 $\frac{3}{4} n$ 之间时，排序树的高度仍然在 $O(\log n)$ ，而总复杂度仍然是 $O(n\log n)$ 。

随机快速排序

前面的分析可以看到，快速排序在特殊情况下性能可能达到 $O(n^2)$ ，比如对于已经排序完成的序列做排序，并以头或尾点作为pivot。而快速排序的一个假定是pivot点总是能将序列分为大致相等的两部分 $L$ 和 $G$ ，这也是我们希望。

引入随机选择pivot的方法，可以近似实现对序列的对等拆分。

定理：随机快速排序的期望运行时间是 $O(n\log n)$ ，其中 $n$ 是序列 $S$ 的长度。

随机快速分析

pivot点的随机选择
选择pivot点的一种经验方式是median-of-three，也就是选择序列 $S$ 的头部、中间和尾部三个点中的值大小在中间的点作为pivot。这种方法比用随机数生成器选择pivot有更小的overhead。对于大数据集，可在更多的点中选median作为pivot。

基于array的in-place快速排序实现

算法的in-place指的是除了初始输入，算法只使用额外的一小部分内存。前面基于linked list的算法实现称不上in-place，因为创建了 $L$ ， $G$ 这些数据结构。基于array实现的快速排序可以实现in-place的快速排序算法，即在输入序列上通过比较和交换，实现对序列的排序，这也是部署中常用的实现方式。该实现方式同样使用了双指针法。

def inplace_quick_sort(S, a, b):
    """Sort the list from S[a] to S[b] inclusive using the quick-sort algorithm."""
    if a > b: return
    left, right, pivot = a, b - 1, S[b]
    while left <= right:
        # scan until reaching value equal or larger than pivot (or right marker)
        while S[left] < pivot and left <= right:
            left += 1
        # scan until reaching value equal or smaller than pivot (or left marker)
        while S[right] > pivot and right >= left:
            right -= 1
        if left <= right:
            S[left], S[right] = S[right], S[left]
            left, right = left + 1, right - 1
    
    # put pivot into its final place (currently marked by left index)
    S[b], S[left] = S[left], S[b]
    # make recursive calls，截止到这里可以看出，
    # 前面步骤是把所有小于pivot的元素放在前面序列中，即S[a:left]，
    # 而大于pivot的元素放在后面序列S[left+1, b]
    inplace_quick_sort(S, a, left-1)
    inplace_quick_sort(S, left+1, b)

demo

inplace快速排序的拆分步骤

注意到inplace快速排序算法在保存计算结果时并没有开辟新的内存用于保存序列，但是每次调用会开辟空间用于存放stack，其正比于回归树的深度，最大可能达到 $n-1$ 。stack的期望深度为 $O(\log n)$ 。当然可以通过特定方法保证stack的深度为 $O(\log n)$ ，基本思路是设计一个非递归的inplace快速排序，使用一个stack用于迭代处理子问题，每个子问题都可以用一堆index来标记子序列边界。每次迭代会弹出最上层的子问题，并将其一分为二，并push这两个新的子问题。其中的关键在于push新子问题时，先push更大的子问题再push小一点的。

堆排序Heap sort

堆顶保存了这个堆中最大/小的元素。通过将序列转化为heap，再依次pop堆顶元素可得到原序列的排序结果。复杂度为 $O(n \log n)$ 。

更多细节参考《堆》。

不同排序算法的对比

稳定排序 stable sorting

当对k-v对做排序时，一个重要问题是如何处理key相等的情况。对序列 $S=((k_0, v_0), \cdots,(k_{n-1}, v_{n-1}))$ 按照 $k_i$ 排序。一个稳定的排序，当两个tuple的 $k_i$ 相同时，他们在排序后的序列中的相对顺序相同。例如，有 $(k_i, v_i)$ 和 $(k_j, v_j)$ ， $i<j$ ，且 $k_i=k_j$ ，在为排序的序列中 $(k_i, v_i)$ 在 $(k_j, v_j)$ 之前，而在排序完成的序列中， $(k_i, v_i)$ 仍然在 $(k_j, v_j)$ 之前，则这个排序是稳定排序。

插入排序 insertion sort

插入排序运行时间是 $O(n+m)$ ，其中 $m$ 是反转次数。插入排序是用于排序小序列的优秀算法，比如不多于50个元素，因其易于实现且小序列未必有很多反转。同样，插入排序对于几乎拍好的序列也很高效。所谓"几乎"，值得是反转次数足够小。但是考虑到 $O(n^2)$ 复杂度，插入排序在上面列举情况意外的情况中表现不佳。

堆排序 heap sort

堆排序在最坏情况下的运行时间是 $O(n\log n)$ ，这对基于比较的排序算法是最优结果。堆排序可以inplace方式执行，是小尺寸和中尺寸序列排序的自然选择。在大尺寸序列的情况下，堆排序被快速排序和并归排序超越。标准的堆排序不是一个稳定的排序，因为其中需要交换元素。

快速排序 quick sort

最坏达到 $O(n^2)$ 的性能表现使得快速排序在实际应用中似乎不是最优的，但我们可以期待其性能达到 $O(n\log n)$ 时间，且实验证明快速排序的性能在很多测试中超越了堆排序和并归排序。快速排序并不会一定实现稳定排序，因为在拆分阶段要交换元素。快速排序在过去几十年中是通用算法和内存型排序算法的默认选项，并被C语言库中引用作为qsort，同时曾经也是Unix系统的排序工具的基础。在Java7以前，快速排序是数组排序的标准算法。

并归排序 merge sort

并归排序在最坏情况下的时间达到 $O(n\log n)$ ，难以将并归改成in-place排序。尽管如此，并归仍然是优秀的解决方案当输入在内存层级中分数不同层时，比如缓存，内存，外部内存，通过减少在内存中转换的总次数。GNU排序工具和最新版的Linux系统中都有赖于多路并归排序的变体。从2003年起，Python list类的排序算法使用了Tim-排序，这是一种混合排序算法，是从下而上的并归排序和插入排序的结合体，并归排序用于初始运行阶段而插入排序用于后续运行。Tim-排序从Java7开始成为数组排序的默认算法。

桶排序bucket sort和根排序radix sort

桶排序和根排序都实现了在特定场景下的线性时间排序 $O(n+N)$ 。

Reference

1 Data Structures and Algorithms in Python, Goodrich and etc