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

文章目录

• 一、快速排序简介
• 二、快速排序可视化
• 三、快速排序实现
• 四、快速排序其他实现
• 五、随机化快速排序

同【常见算法Python描述】基于分治思想的归并排序简介与实现中的归并排序一样，快速排序是分治思想的另一个典型应用。

一、快速排序简介

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

• 分：如果序列$s$仅有0个或1个元素，因为序列已有序，则直接返回$s$即可；否则（序列至少有2个元素），首先从序列$s$中选择出一个特定的元素$x$，且称其为基准值，通常会将序列$s$的最后一个元素选为基准值；然后将序列$s$中所有元素移动至三个子序列中：
  • $lt$：保存序列$s$中所有小于$x$的元素；
  • $eq$：保存序列$s$中所有等于$x$的元素；
  • $gt$：保存序列$s$中所有大于$x$的元素；
• 治：对$lt$和$gt$进行递归排序；
• 合：按照$lt$、$eq$和$gt$的顺序将其中的元素放回原序列$s$中。

二、快速排序可视化

为便于读者理解，同归并排序一样，我们也可以通过一个二叉树来描述快速排序的具体过程，即一个节点代表一次递归处理，输入为待排序的子序列，输出为该子序列的已排序形式，类似地我们将其称为快速排序树。

同样地，对于一个具有8个元素的待排序列，下面先从总体上给出任意节点递归调用返回前后所代表的序列状态，然后给出快速排序每一步的具体过程。

对于上图，需要说明的是，图(a)表示了每个节点输入的待排（子）序列，图(b)表示每个节点所代表的递归调用返回后产生的已排序子序列，其中所有粗体的均为基准值。

下面给出快速排序的详细步骤，且同样对图例作如下约定：

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

三、快速排序实现

1. 链式队列实现快速排序

下面给出了当待排序的序列为链式结构的队列时，对其使用快速排序的代码实现，其中：

• 选择队头元素作为基准值pivot，因为其获取最便捷；
• 根据待排序列$s$的元素和基准值pivot的大小关系，$s$的所有元素被分成了$lt$、$eq$、$gt$三个子序列。

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 quick_sort(s: LinkedQueue):
    """Sort the elements of queue S using the quick-sort algorithm."""
    num = len(s)
    if num < 2:
        return  # 序列已有序
    # 分——divide
    pivot = s.first()  # 使用队头元素作为基准值
    lt = LinkedQueue()
    eq = LinkedQueue()
    gt = LinkedQueue()
    while not s.is_empty():  # 将序列s分为lt、eq和gt三个部分
        if s.first() < pivot:
            lt.enqueue(s.dequeue())
        elif s.first() > pivot:
            gt.enqueue(s.dequeue())
        else:
            eq.enqueue(s.dequeue())
    # 治——conquer
    quick_sort(lt)
    quick_sort(gt)
    # 合——concatenate
    while not lt.is_empty():
        s.enqueue(lt.dequeue())
    while not eq.is_empty():
        s.enqueue(eq.dequeue())
    while not gt.is_empty():
        s.enqueue(gt.dequeue())

2. 快速排序时间复杂度分析

快速排序的期望时间复杂度为$O(nlogn)$。

四、快速排序其他实现

1. 双端队列实现快速排序

本文前面给出的快速排序算法实现假定待排序列是我们自己实现的LinkedQueue类，而Python的collections模块中内置了一个双端队列数据结构deque，我们可以将其用作一个普通队列，然后对其中的所有元素使用快速排序算法，具体实现如下：

from collections import deque


def quick_sort(s: deque):
    """对序列s使用快速排序算法进行排序"""
    num = len(s)
    if num < 2:
        return
    pivot = s[-1]
    lt = deque()
    eq = deque()
    gt = deque()
    while len(s) != 0:
        if s[0] < pivot:
            lt.append(s.popleft())
        elif s[0] > pivot:
            gt.append(s.popleft())
        else:
            eq.append(s.popleft())
    quick_sort(lt)
    quick_sort(gt)
    while len(lt) != 0:
        s.append(lt.popleft())
    while len(eq) != 0:
        s.append(eq.popleft())
    while len(gt) != 0:
        s.append(gt.popleft())


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])
    quick_sort(s)
    print(list(s))  # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 19, 20, 23]

上述实现的优点在于只要待排序列是可迭代对象（如：list、tuple），均可以先将其转化为deque对象然后应用上述quick_sort函数进行排序。

2. 原地快速排序实现

五、随机化快速排序

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