【常见算法Python描述】基于分治思想的归并排序简介与实现

文章目录

• 一、分治设计模式
• 二、使用分治排序
• 三、归并排序典型实现
• 四、其他归并排序实现

一、分治设计模式

在介绍归并排序之前，我们先介绍一种名为分治（divide-and-conquer）的算法设计模式，分治思想实际上是递归的典型应用，使用分治思想一般分为以下几个步骤：

• 分（divide）：如果算法输入的序列数量小于某阈值（如：仅一个或两个元素），则直接直接对问题进行求解然后返回结果。否则，将输入序列分为多个互不相交的子集；
• 治（conquer）：递归式求解每一个互不相交的子集；
• 合：将对子集求解的结果进行合并得到原问题的结果。

二、使用分治排序

首先，我们从理论上分析如何使用分治的思想来对一个序列实现归并排序，而不关心待排序的序列究竟是列表还是链表形式，后续我们将分别给出基于列表或链表的实现。

1. 归并排序简介

假设给定具有$n$个元素的序列$s$，则对其应用分治思想通过归并算法排序可以大致分为以下几个步骤：

• 分：如果序列$s$仅有0个或1个元素，因为序列已有序，则直接返回$s$即可；否则（序列至少有2个元素），将序列$s$中所有元素移动至两个序列$s_1$和$s_2$中，每一个序列都大致包含$s$中的一半元素，即$s_1$中包含$\lfloor n/2\rfloor$个元素，$s_2$中包含$\lceil n/2\rceil$个元素；
• 治：对$s_1$和$s_2$进行递归排序；
• 合：将已排好序的$s_1$和$s_2$中的元素放回原序列$s$中。

2. 归并排序可视化

为便于理解，下面通过二叉树T图绘归并排序的流程，我们将该二叉树称为归并排序树，其中根节点代表对原序列$s$进行归并排序的递归调用操作，子节点代表对两个子序列$s_1$和$s_2$进行递归调用操作，而叶子节点则代表对递归出口处的返回。具体地，下图(a)表示每个节点处的输入序列，图(b)表示每个节点处的输出序列。

值得注意的是，如上图所示，由于待排序的序列在每次递归后数量大致减半，因此归并排序树的高度大致为$logn$。

上图主要聚焦于用二叉树描述归并排序时每个节点的输入和输出情况，下面通过图示具体给出归并排序的每一个具体步骤，为便于理解，下图通过不同线条区分每个节点当前所处的递归调用状态：

• 虚线节点表示当前还未发生递归调用；
• 粗实线节点表示当前正在进行递归调用；
• 细实线空节点表示递归调用已返回；
• 其他节点表示等待递归调用返回。

需要注意的是，鉴于篇幅原因且为了避免重复，上述步骤(m)和(n)之间省略多次调用的图示。

三、归并排序典型实现

由上述图示可知，实现归并排序时，将待排序的序列分为分为两个部分（分）以及进行递归调用（治）的两个步骤都很简单，难点在于如何将两个已排序的子序列合并（合）成一个有序序列。

1. 普通列表实现归并排序

针对上述难点，当待排序的序列为列表时，先给出一个名为merge的函数实现，该函数负责将两个已排序的子序列$s_1$和$s_2$合并为有序的$s$。具体地，在while语句的每一次迭代中，根据不同的条件确定将$s_1$还是$s_2$的下一个元素拷贝进$s$中。

def merge(s1, s2, s):
    """将有序列表s1和s2合并为一个有序列表"""
    i = j = 0
    while i + j < len(s):
        if j == len(s2) or (i < len(s1) and s1[i] < s2[j]):
            s[i + j] = s1[i]  # 将s1的第i个元素拷贝为s的下一个元素
            i += 1
        else:
            s[i + j] = s2[j]  # 将s2的第j个元素拷贝为s的下一个元素
            j += 1

下图给出了merge函数某一次迭代的过程，其中变量$i$和$j$分别代表已经从序列$s_1$和$s_2$拷贝至$s$的元素个数，假定$s_1$和$s_2$此时都至少有一个未被拷贝的元素，则本次将拷贝二者中较小的那一个。由于$i+j$个元素已经被拷贝，因此下一个元素将被拷贝至$s[i+j]$处。

通过使用上述merge函数，针对列表形式待排序列，对其应用基于分治思想的归并排序实现如下：

def merge_sort(s):
    """对列表s使用归并排序算法"""
    num = len(s)
    if num < 2:
        return
    # 分（divide）
    mid = num // 2
    s1 = s[0:mid]
    s2 = s[mid:num]
    # 治（conquer）
    merge_sort(s1)
    merge_sort(s2)
    # 合并结果（merge results）
    merge(s1, s2, s)

2. 归并排序复杂度分析

为分析上述对于归并排序merge_sort的最坏复杂度，首先需要分析merge函数的复杂度，我们假定$n_1$和$n_2$分别代表子序列$s_1$和$s_2$的元素个数，显然while循环的每一次迭代都是$O(1)$时间复杂度，因此merge函数的时间复杂度为$O(n_1+n_2)$。

基于上述结论，下面来分析merge_sort函数的最坏时间复杂度。假定给定的待排序列表有$n$个元素，这里分析merge_sort的最坏复杂度时只需考虑每一次递归调用中的分和合的操作，而无需考虑其中的两次merge_sort的递归调用。

具体地，上述描述归并排序的图示可以帮助我们得出merge_sort函数的最坏时间复杂度：

由于假定在归并排序树T的一个节点$v$处的操作代表一次递归调用，此时merge_sort中分的步骤所需时间很直观，该步骤使用切片操作将输入序列分为两半，显然其时间复杂度和输入序列的元素数量呈正比；另外，上述我们也分析了合的步骤所使用的merge函数其时间复杂度和合并后序列元素个数呈正比。

基于上述讨论，如果假设节点$v$在归并排序树中的深度为$i$，则在节点$v$处操作的时间复杂度为$O(n/2^i)$，则merge_sort的时间复杂度等于所有节点处递归调用时间复杂度之和。

有趣的是，归并排序树T深度为$i$的位置恰好共有$2^i$个节点，因此深度为$i$处的所有节点处的递归调用时间复杂度为$O(2^i\cdot n/2^i)$，即为$O(n)$，又由于归并排序树的高度为$\lceil logn\rceil$。

因此，在待排序列中元素可以$O(1)$时间复杂度进行两两的大小比较时，归并排序的最坏时间复杂度为$O(nlogn)$。

四、其他归并排序实现

1. 链式队列实现归并排序

当待排序的序列以链式结构给出时，对其使用归并排序的实现和上述实现类似，下面给出了当待排序的序列为链式结构的队列时，对其使用归并排序的实现：

class Empty(Exception):
    """尝试对空队列进行删除操作时抛出的异常"""
    pass


class _Node:
    """节点类"""

    def __init__(self, element, next=None):
        """
        :param element: 节点代表的对象元素
        :param next: 节点对象中用于指向下一个节点的实例属性
        """
        self.element = element
        self.next = next


class LinkedQueue:
    """使用单链表保存对象元素实现的队列数据结构"""
    def __init__(self):
        """创建一个空队列"""
        self._head = None  # 初始化头节点
        self._tail = None  # 初始化尾节点
        self._size = 0  # 队列元素个数

    def __len__(self):
        """
        返回队列中的元素个数
        :return: 元素个数
        """
        return self._size

    def is_empty(self):
        """
        如果队列为空则返回True
        :return: 队列是否为空的状态
        """
        return self._size == 0

    def first(self):
        """
        返回但不删除队头元素
        :return: 队头元素
        """
        if self.is_empty():
            raise Empty('当前队列为空！')
        return self._head.element

    def enqueue(self, element):
        """
        向队列尾部插入对象元素
        :param element: 待插入队列尾部的对象元素
        :return: None
        """
        node = _Node(element)
        if self.is_empty():
            self._head = node
        else:
            self._tail.next = node
        self._tail = node  # 使新入队尾的元素成为尾节点
        self._size += 1

    def dequeue(self):
        """
        删除并返回队头的节点，并返回其中的对象元素，如此时队列为空则抛出异常
        :return: 队头节点的element域
        """
        if self.is_empty():
            raise Empty('队列为空！')
        ans = self._head.element
        self._head = self._head.next
        self._size -= 1
        if self.is_empty():  # 如果执行本次出对操作时队列中仅有一个节点，则此时该节点同时也是尾节点，需对此做处理
            self._tail = None
        return ans


def merge(s1: LinkedQueue, s2: LinkedQueue, s: LinkedQueue):
    """将两个有序队列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_sort(s: LinkedQueue):
    """将队列s中的元素使用归并排序进行排序"""
    num = len(s)
    if num < 2:
        return
    # 分（divide）
    s1 = LinkedQueue()
    s2 = LinkedQueue()
    while len(s1) < num // 2:
        s1.enqueue(s.dequeue())
    while not s is_empty():
        s2.enqueue(s.dequeue())
    # 治（conquer）
    merge_sort(s1)
    merge_sort(s2)
    # 合并结果
    merge(s1, s2, s)

由于上述LinkedQueue的所有操作时间时间复杂度均为$O(1)$，因此merge_sort的最坏时间复杂度仍为$nlogn$。

2. 双端队列实现归并排序

上述实现基于我们自己实现的LinkedQueue类，而Python的collections模块中内置了一个双端队列数据结构deque，我们可以将其用作一个普通队列，然后对其中的所有元素使用归并排序算法，具体实现如下：

from collections import deque


def merge(s1: deque, s2: deque, s: deque):
    """将两个有序队列s1和s2合并进一个空队列中"""
    while not len(s1) == 0 and not len(s2) == 0:
        if s1[0] < s2[0]:
            s.append(s1.popleft())
        else:
            s.append(s2.popleft())
    while not len(s1) == 0:
        s.append(s1.popleft())
    while not len(s2) == 0:
        s.append(s2.popleft())


def merge_sort(s: deque):
    """将队列s中的元素使用归并排序进行排序"""
    num = len(s)
    if num < 2:
        return
    # 分（divide）
    s1 = deque()
    s2 = deque()
    while len(s1) < num // 2:
        s1.append(s.popleft())
    while not len(s) == 0:
        s2.append(s.popleft())
    # 治（conquer）
    merge_sort(s1)
    merge_sort(s2)
    # 合并结果
    merge(s1, s2, s)


if __name__ == '__main__':
    lst = [8, 3, 6, 1, 7, 4, 5, 10, 2, 9, 13, 18, 14, 20, 23, 19, 12]
    s = deque(lst)
    print(s)  # deque([8, 3, 6, 1, 7, 4, 5, 10, 2, 9, 13, 18, 14, 20, 23, 19, 12])
    merge_sort(s)
    print(list(s))  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 23]

需要注意的是：

• 当将內置双端队列deque视为普通队列时，popleft方法即相当于LinkedQueue的队头元素出队方法dequeue，append方法即相当于LinkedQueue的元素从队尾入队操作enqueue；
• deque可接收列表、元组等可迭代对象作为参数，从而实现对其进行排序。

3. 迭代法实现归并排序

当待排序的序列为列表时，对其使用归并排序还有一种非递归的实现方式，其最坏时间复杂度也为$nlogn$，这种非递归的实现相较递归实现方式而言，时间和空复杂度更优，原因在于非递归实现无需递归实现所需的额外状态维持的开支以及每一层的临时空间。

非递归实现的主要流程为，当给定输入的待排序列，首先将两两相邻的元素合并为两个一组的序列，此时序列是两两有序的；然后将两两相邻的有序元素对合并为四个有序元素为一组的序列；接着是八个有序元素为一组的序列，直到最终整个序列有序。

在实现中，我们还声明了另外一个列表用以保存每次迭代合并后得到的序列。

import math


def merge(src, dest, start, inc):
    """将列表src[start:start+inc]和src[start+inc:start+2 inc]合并至result中."""
    end1 = start + inc  # 第一组元素的索引上界
    end2 = min(start + 2 * inc, len(src))  # 第二组元素的索引上界
    x, y, z = start, start + inc, start  # 用于定位第一组、第二组以及result元素所处位置的索引
    while x < end1 and y < end2:
        if src[x] < src[y]:
            dest[z] = src[x]  # 从第一组元素中拷贝元素
            x += 1
        else:
            dest[z] = src[y]  # 从第二组元素中拷贝元素
            y += 1
        z += 1
    if x < end1:
        dest[z:end2] = src[x:end1]  # 拷贝第一组中的所剩元素
    elif y < end2:
        dest[z:end2] = src[y:end2]  # 拷贝第二组中的所剩元素


def merge_sort(s):
    """对列表使用归并排序算法"""
    num = len(s)
    logn = math.ceil(math.log(num, 2))
    src, dest = s, [None] * num
    for i in (2 ** k for k in range(logn)):  # 第i次迭代会生成2i个有序元素为一组的序列
        for j in range(0, num, 2 * i):  # 每次迭代将合并两个元素数量为i的有序元素组
            merge(src, dest, j, i)
        src, dest = dest, src  # 确保src总是引用更加有序的序列
    if s is not src:  # 如果最终src和s不引用同一个序列，则需要做额外的切片拷贝操作
    # if s is dest:
        s[0:num] = src[0:num]

if __name__ == '__main__':
    s = [8, 3, 6, 1, 7, 4, 5, 10, 2, 9, 13, 18, 14, 20, 23, 19, 12]
    merge_sort(s)
    print(s)  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 23]

本文地址：https://blog.csdn.net/weixin_37780776/article/details/110846787