排序算法之：快速排序的分区策略优化——荷兰国旗问题与三向切分（Dutch National Flag / 3-Way Partitioning）

题目描述

给定一个包含重复元素的整数数组，使用快速排序进行排序。传统的快速排序分区（如 Lomuto 或 Hoare 分区）在遇到大量重复元素时性能会退化到 O(n²)。请实现三向切分（3-Way Partitioning）优化，将数组分为三个部分：小于基准、等于基准、大于基准，从而高效处理重复元素。要求详细说明算法步骤，并分析其优势。

循序渐进讲解

1. 问题分析

普通快速排序选择一个基准（pivot）后将数组分为两个子数组：≤基准 和 >基准（Lomuto）或 <基准 和 ≥基准（Hoare）。当数组中存在大量重复元素时，这些方法会导致分区不平衡，因为所有等于基准的元素会被分到同一侧，造成递归树深度增加，性能下降。

三向切分的目标是将数组分为三部分：

• 左侧：所有小于基准的元素
• 中间：所有等于基准的元素
• 右侧：所有大于基准的元素

这样，中间部分的所有相等元素在后续递归中可以直接忽略，因为它们已经在最终位置。

2. 算法步骤详解

我们采用 Edsger Dijkstra 提出的“荷兰国旗问题”解法思路，用三个指针来维护四个区域。假设我们选择数组第一个元素作为基准 pivot。

定义三个指针：

• low：初始指向数组起始位置。它指向小于基准区域的下一个位置。
• mid：初始指向数组起始位置。用于遍历数组。
• high：初始指向数组末尾。它指向大于基准区域的前一个位置。

初始状态：

[ pivot | 未处理区域 ]
 low/mid            high

循环不变式（Loop Invariant）：
在每次循环开始时，数组被划分为四个连续区域：

1. arr[0..low-1]：所有元素小于基准。
2. arr[low..mid-1]：所有元素等于基准。
3. arr[mid..high]：未处理的元素。
4. arr[high+1..n-1]：所有元素大于基准。

处理规则：

• 如果 arr[mid] < pivot：将 arr[mid] 与 arr[low] 交换，然后 low++ 和 mid++。
  • 因为 arr[low] 是等于基准区域的第一个元素（或就是 arr[mid] 本身），交换后，小于基准区域扩大了。
• 如果 arr[mid] == pivot：mid++，等于基准区域自然扩大。
• 如果 arr[mid] > pivot：将 arr[mid] 与 arr[high] 交换，然后 high--。
  • 注意：交换后 arr[mid] 是来自未处理区域末尾的新元素，尚未检查，所以 mid 不变。

循环终止条件： 当 mid > high 时，表示未处理区域为空，循环结束。

3. 举例演示

假设数组为 [3, 1, 4, 3, 2, 3, 5, 3]，选择 pivot = arr[0] = 3。

初始：

[3, 1, 4, 3, 2, 3, 5, 3]
 l/m                  h

步骤1： arr[mid]=3 == pivot → mid++

[3, 1, 4, 3, 2, 3, 5, 3]
 l   m               h

步骤2： arr[mid]=1 < pivot → 交换 arr[mid] 和 arr[low]，low++, mid++

[1, 3, 4, 3, 2, 3, 5, 3]
    l/m             h

步骤3： arr[mid]=4 > pivot → 交换 arr[mid] 和 arr[high]，high--

[1, 3, 3, 3, 2, 3, 5, 4]
    l/m           h

步骤4： arr[mid]=3 == pivot → mid++

[1, 3, 3, 3, 2, 3, 5, 4]
    l   m         h

步骤5： arr[mid]=2 < pivot → 交换 arr[mid] 和 arr[low]，low++, mid++

[1, 2, 3, 3, 3, 3, 5, 4]
       l/m       h

步骤6： arr[mid]=3 == pivot → mid++

[1, 2, 3, 3, 3, 3, 5, 4]
       l   m     h

步骤7： arr[mid]=5 > pivot → 交换 arr[mid] 和 arr[high]，high--

[1, 2, 3, 3, 3, 3, 4, 5]
       l   m   h

步骤8： arr[mid]=3 == pivot → mid++，此时 mid > high，循环结束。

最终分区结果：

• 小于3的区域：[1, 2] (索引 0-1)
• 等于3的区域：[3, 3, 3, 3] (索引 2-5)
• 大于3的区域：[4, 5] (索引 6-7)

递归地对小于和大于的两个子数组进行三向切分快速排序。

4. 算法实现（伪代码）

function threeWayQuickSort(arr, left, right):
    if left >= right:
        return
    pivot = arr[left]
    low = left
    mid = left
    high = right
    
    while mid <= high:
        if arr[mid] < pivot:
            swap arr[low], arr[mid]
            low++
            mid++
        else if arr[mid] == pivot:
            mid++
        else:  # arr[mid] > pivot
            swap arr[mid], arr[high]
            high--
    
    # 递归排序小于和大于区域
    threeWayQuickSort(arr, left, low - 1)
    threeWayQuickSort(arr, high + 1, right)

5. 算法优势分析

1. 高效处理重复元素：当数组中存在大量重复键时，所有等于基准的元素在一次分区后就直接排好序，不再参与后续递归，避免了不必要的递归调用。
2. 时间复杂度优化：
   • 最好/平均情况：O(n log n)
   • 最坏情况（所有元素相等）：O(n)，因为每次分区后，中间部分包含所有元素，递归终止。这是对传统快速排序 O(n²) 的极大改进。
3. 原地排序：只需要常数级别的额外空间（递归栈除外）。

6. 对比传统快速排序

• 传统 Lomuto 分区：将所有重复基准值放在一侧，导致分区极度不平衡。
• 三向切分：将重复基准值集中在中间，使剩余待排序子数组规模显著减小。

7. 应用场景

• 数组中包含大量重复键的情况（例如：按性别、年龄分组等）。
• 需要稳定排序的近似场景（三向切分不是稳定排序，但可以减少相同键的移动）。
• 在实现通用排序库时常用（如 Java 7+ 中 Arrays.sort() 对基本类型使用了双轴快排的变种，其中包含三向切分思想）。

通过这种优化，快速排序在面对重复元素时的鲁棒性大大增强，成为实际应用中最高效的通用排序算法之一。