异常教程

双路快速排序（超详细）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言

在编程世界中，排序算法是基础且重要的工具之一。快速排序作为经典的分治算法，因其平均时间复杂度为 O(n log n) 的高效性，被广泛应用于实际场景。然而，当遇到大量重复元素时，传统快速排序的性能可能显著下降。此时，“双路快速排序”便展现出其独特的优势。本文将通过循序渐进的方式，从快速排序的基本原理出发，逐步解析双路快速排序的实现逻辑，并通过案例与代码示例，帮助读者理解这一算法的核心思想与应用场景。

快速排序的基础逻辑：分治与基准值

快速排序的核心思想是通过“分治法”将一个大问题拆解为多个小问题。其关键步骤包括：

  1. 选择基准值（Pivot）：从数组中随机或按规则选取一个元素作为基准。
  2. 分区操作（Partition）：将数组分为两部分，一部分元素小于基准，另一部分大于基准。
  3. 递归排序：对左右两个子数组重复上述过程，直到子数组长度为 1 或 0。

例如，假设有一个未排序的数组 [5, 3, 8, 4, 2]，选择第一个元素 5 作为基准值：

  • 分区后，左边子数组 [3, 4, 2] 中所有元素均小于 5，右边子数组 [8] 中所有元素均大于 5。
  • 接着对 [3, 4, 2] 和 [8] 分别递归排序。

但这一过程在元素重复较多时会出现问题。例如，若数组为 [5, 5, 5, 5]，传统快速排序的分区操作会将所有元素归为一侧，导致时间复杂度退化为 O(n²)。

双路快速排序的诞生：解决重复元素的困境

双路快速排序的改进点在于优化分区操作，通过双指针技术将数组划分为三个区域：

  1. 小于基准值的区域：位于数组的左端。
  2. 等于基准值的区域：位于中间，无需移动。
  3. 大于基准值的区域：位于数组的右端。

其核心逻辑如下：

  • 使用两个指针 i 和 j，初始时 i 指向数组起始位置，j 指向末尾。
  • i 从左向右遍历，寻找第一个大于等于基准值的元素；
  • j 从右向左遍历，寻找第一个小于等于基准值的元素；
  • 当 i 和 j 交错时终止循环，并交换它们指向的元素。

通过这一机制，双路快速排序能高效处理重复元素，避免单路快速排序因重复值导致的性能下降。

双路快速排序的分区过程：一个比喻

想象你和朋友在整理一堆快递包裹，目标是将包裹按重量分成轻、中、重三类：

  1. 双路指针的分工：你从左边开始检查包裹，遇到“过重”的直接跳过；朋友从右边开始检查，遇到“过轻”的直接跳过。
  2. 交换与移动：当你们同时找到一个“过轻”和“过重”的包裹时，交换它们的位置，并继续向中间移动。
  3. 循环终止条件：当你们相遇时，停止交换，此时所有轻包裹在左，重包裹在右，中间可能有多个“中等重量”的包裹。

这一过程完美体现了双路快速排序如何通过“双指针协作”高效划分区域。

双路快速排序的实现细节与代码示例

以下是 Python 语言中双路快速排序的实现代码：

def quick_sort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort(arr, low, pivot_index)  
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[low]  # 选择第一个元素作为基准值
    i = low           # 左指针初始位置
    j = high          # 右指针初始位置
    
    while True:
        # 找到第一个大于等于基准的元素
        while arr[i] < pivot:
            i += 1
        # 找到第一个小于等于基准的元素
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j  # 返回分区点
        # 交换元素
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1

关键点解析：

  1. 基准值选择：这里选择数组的第一个元素作为基准，也可随机选择以优化最坏情况。
  2. 指针移动逻辑：
    • i 的移动条件是 arr[i] < pivot，确保左边区域始终小于基准。
    • j 的移动条件是 arr[j] > pivot，确保右边区域始终大于基准。
  3. 终止条件：当 i >= j 时，说明指针已交错，此时 j 的位置即为分区点。

单路 vs 双路 vs 三路快速排序的对比

算法类型适用场景时间复杂度（最坏）处理重复元素能力
单路快速排序元素无重复或重复较少O(n²)效率显著下降
双路快速排序元素有较多重复值O(n log n)稳定且高效
三路快速排序元素重复极多（如大量相同值）O(n log n)最优，完全分离三区域

对比分析：

  • 单路快速排序在处理重复元素时，所有等于基准值的元素会被推到数组一端，导致分区不均，效率降低。
  • 双路快速排序通过双指针协作，将等于基准值的元素保留在中间区域，避免了单路的缺陷。
  • 三路快速排序进一步将数组划分为“小于”“等于”“大于”三个区域，适合极端重复场景，但实现复杂度更高。

双路快速排序的优化与实际应用

优化点：基准值选择与随机化

在实际代码中，选择固定位置（如第一个元素）作为基准值可能导致最坏情况（如数组已排序）。可以通过随机选择基准值来降低这种风险：

import random  

def partition(arr, low, high):
    # 随机选择基准值并交换到起始位置
    pivot_index = random.randint(low, high)
    arr[low], arr[pivot_index] = arr[pivot_index], arr[low]
    pivot = arr[low]
    # 后续逻辑与原代码相同

应用场景示例：处理用户评分数据

假设有一个电商平台的用户评分列表 [4, 5, 3, 5, 2, 5, 4]，需快速排序以分析高分与低分分布。使用双路快速排序：

  1. 选择基准值 4，分区后得到 [3, 2]、[4,5,5,5,4]、[5]。
  2. 递归排序左右子数组，最终得到 [2, 3, 4, 4, 5, 5, 5]。
    这一过程在重复值较多时（如多个 5）仍能保持线性对数时间复杂度。

结论

双路快速排序通过双指针分区策略，在保持快速排序高效性的同时，解决了传统方法在重复元素场景下的性能瓶颈。其核心在于通过“指针协作”将数组划分为明确的三个区域，从而避免因元素重复导致的时间复杂度退化。对于编程初学者而言，理解这一算法需要结合分治思想与指针操作的细节；中级开发者则可进一步探索其优化空间，如基准值随机化、与三路快速排序的结合等。掌握这一算法，不仅能提升编程技能，更能为解决实际数据处理问题提供有力工具。

希望本文能帮助读者深入理解双路快速排序的原理与实践，并在实际开发中灵活应用这一高效算法。

最新发布

查看更多文章