排序算法之：快速排序的“三路划分”（Three-Way Partitioning）优化——处理大量重复元素的高效策略

题目描述

在快速排序中，当待排序数组包含大量重复元素时，传统的双路划分（如Hoare或Lomuto分区）算法效率会显著下降，时间复杂度可能退化到接近O(n²)。原因是传统分区方法每次递归只能将数组划分为“小于基准值”和“大于等于基准值”（或类似）的两部分，导致大量等于基准值的元素被递归地包含在一侧子数组中，无法快速缩小问题规模。

本题目要求我们深入理解并实现快速排序的三路划分优化（Three-Way Partitioning，或称Dijkstra的“荷兰国旗问题”解法）。该算法通过一次遍历，将数组划分为三个区域：所有小于基准值pivot的元素、所有等于基准值pivot的元素，以及所有大于pivot的元素。这样，在下一次递归调用时，我们可以直接忽略所有等于基准值的元素，因为它们已经处于最终的正确位置上。这对于存在大量重复键的数组（例如，对人口按年龄排序，年龄重复很多）能带来显著的性能提升。

循序渐进讲解

第一步：理解问题与直觉

1. 传统快速排序的问题回顾：

   • 假设我们有一个数组：[3, 2, 3, 5, 3, 1, 3]，选择第一个元素3作为基准值（pivot）。
   • Lomuto分区后可能得到：[2, 1, 3, 3, 3, 3, 5]（基准值最终在索引2的位置）。
   • 然后我们对[2, 1]和[3, 3, 3, 5]两个子数组递归排序。注意，右侧子数组[3, 3, 3, 5]中仍然包含三个等于基准值3的元素。在后续递归中，这些3会被反复作为基准值选中并处理，造成不必要的比较和交换。

2. 三路划分的目标：

   • 我们的目标是经过一次划分后，数组被清晰地分成三部分：[ < pivot ]， [ == pivot ]， [ > pivot ]。
   • 对于上面的例子，理想的一次三路划分结果应该是：[2, 1, 3, 3, 3, 3, 5]（严格来说，等于pivot的区域是连续的）。这样，我们只需要对[2, 1]（小于区）和[5]（大于区）递归排序，而中间连续的[3, 3, 3, 3]完全不需要再处理。
   • 当重复元素非常多时，这个优化能极大地减少递归深度和比较次数。

第二步：三路划分的算法设计

我们使用三个指针来维护四个区域：

• low：数组的起始索引（通常为0），也是我们遍历的起始点。
• i：遍历指针，从low开始向右移动。
• lt（less than）：指向小于区的末尾。保证arr[low..lt-1]中的所有元素都小于pivot。
• gt（greater than）：指向大于区的起始。保证arr[gt..high]中的所有元素都大于pivot。
• 初始状态：lt = low, gt = high, i = low。
• 基准值pivot可以选择数组中的任意元素，为简单起见，我们选择arr[low]。

划分过程中，我们将维持以下不变式（循环不变式）：

1. arr[low..lt-1] 中的元素 < pivot。
2. arr[lt..i-1] 中的元素 == pivot。
3. arr[i..gt] 中的元素是尚未处理的区域。
4. arr[gt+1..high] 中的元素 > pivot。

第三步：逐步推演划分过程

假设数组为：arr = [3, 2, 3, 5, 3, 1, 3]，索引low=0, high=6。

1. 选择pivot = arr[low] = 3。

2. 初始化：lt = 0, i = 0, gt = 6。

   • 未处理区：[0..6] (i=0, gt=6)
   • 小于区：空 ([0..-1])
   • 等于区：空 ([0..-1])
   • 大于区：空 ([7..6])

3. 开始遍历，只要 i <= gt：

   • 情况A：arr[i] < pivot
     • 将arr[i]与arr[lt]交换（arr[lt]是等于区的第一个元素，或者就是当前i本身）。
     • 增加lt和i。这意味着这个小于pivot的元素被放到了小于区的末尾，并且小于区扩大了一位。由于交换到i位置的是原来等于区的元素（或它本身），它属于未处理区或等于区，所以i可以前进。
     • 例子：i=0时，arr[0]=3不小于pivot(3)。跳过。
     • i=1时，arr[1]=2 < 3。交换arr[1]和arr[lt=0] => [2, 3, 3, 5, 3, 1, 3]。lt++变为1，i++变为2。
   • 情况B：arr[i] == pivot
     • 只需i++。该元素自然包含在等于区内，等于区自动向右扩张（因为i在等于区末尾）。
     • 例子：i=2时，arr[2]=3 == 3。i++变为3。
     • i=3时，arr[3]=5 > 3，属于情况C。
   • 情况C：arr[i] > pivot
     • 将arr[i]与arr[gt]交换。
     • gt--。注意，此时i不增加，因为从gt位置交换过来的元素是尚未处理的，需要在下一次循环中检查。
     • 例子：i=3, gt=6。交换arr[3]=5和arr[6]=3 => [2, 3, 3, 3, 3, 1, 5]。gt--变为5。i保持为3。
   • 继续检查i=3，arr[3]=3 == 3，属于情况B：i++变为4。
   • i=4，arr[4]=3 == 3，i++变为5。
   • i=5，arr[5]=1 < 3，属于情况A：交换arr[5]和arr[lt=1] => [2, 1, 3, 3, 3, 3, 5]。lt++变为2，i++变为6。
   • i=6，此时i=6，gt=5，条件i <= gt为假，循环结束。

4. 最终状态：

   • lt = 2, gt = 5。
   • arr[0..lt-1] = arr[0..1] = [2, 1] 是 小于区。
   • arr[lt..gt] = arr[2..5] = [3, 3, 3, 3] 是 等于区（已排好序）。
   • arr[gt+1..high] = arr[6..6] = [5] 是 大于区。
   • 结果完全符合预期。接下来只需递归排序小于区[0,1]和大于区[6,6]。

第四步：算法实现（伪代码/代码框架）

def three_way_quicksort(arr, low, high):
    if low >= high:
        return
    # 选择pivot（可优化为随机选择或三数取中）
    pivot = arr[low]
    lt = low      # 小于区的右边界（开区间）
    gt = high     # 大于区的左边界（开区间）
    i = low       # 当前遍历指针

    while i <= gt:
        if arr[i] < pivot:
            arr[i], arr[lt] = arr[lt], arr[i]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
            # 注意：这里i不增加，因为交换过来的arr[gt]是未处理的
        else: # arr[i] == pivot
            i += 1

    # 递归排序小于区和大于区
    three_way_quicksort(arr, low, lt - 1)
    three_way_quicksort(arr, gt + 1, high)

第五步：复杂度与特性分析

1. 时间复杂度：

   • 最佳/平均情况：O(n log n)。当重复元素不多时，行为类似经典快速排序。
   • 最坏情况：当所有元素都不同且每次选择的pivot都是最值，退化为O(n²)。但通过随机选择pivot可以极大地避免。
   • 关键优势：大量重复元素：当数组中有大量重复键时，时间复杂度可接近O(n)。因为每次划分都能将等于pivot的一大块元素直接排除在后续递归之外。对于所有元素都相同的情况，只需一次遍历(O(n))，无递归。

2. 空间复杂度：主要是递归调用栈，平均O(log n)，最坏O(n)。

3. 稳定性：上述实现不是稳定的，因为交换操作可能改变相等元素的相对顺序。如果需要稳定排序，需使用其他方法（如归并排序）。

4. 与双路划分对比：

   • 双路划分（如Hoare）在平均情况下常数因子可能更小，代码更简洁。
   • 三路划分在处理重复键时优势巨大，是许多现代排序库（如Java的Arrays.sort()对基本类型使用Dual-Pivot Quicksort的变体，其中就包含三路划分的思想）的标准组成部分。

总结

三路划分快速排序通过将数组精确地划分为“小、等、大”三个区域，优雅地解决了传统快速排序在处理含大量重复元素数组时的性能瓶颈。其核心在于维护三个指针(lt, i, gt)和四个区域的不变式，通过一次线性扫描完成划分。理解和掌握这一优化，对于深入认识快速排序的适应性和工程实践中的排序选择至关重要。