三路快速排序如何优化大量重复元素的场景？

简化版

三路快速排序把数组按 pivot 分成三段：小于 pivot、等于 pivot、大于 pivot。

普通快排遇到大量重复元素时，可能反复处理等于 pivot 的元素，效率变差。三路快排一次 partition 就把等于 pivot 的元素集中到中间，后续只递归左右两边。

它特别适合重复值很多的数组。

详细版

三路划分维护三个区域：

[left, lt)       < pivot
[lt, i)          == pivot
[i, gt]          unknown
(gt, right]      > pivot

扫描时：

nums[i] < pivot：和 lt 交换，lt++，i++
nums[i] == pivot：i++
nums[i] > pivot：和 gt 交换，gt--

场景	普通快排	三路快排
元素互异	表现接近	表现接近
重复元素很多	可能重复递归	更高效

完整版教学

1. 普通快排在重复元素下的问题

普通快排通常把数组分成两部分：

<= pivot
> pivot

或者：

< pivot
>= pivot

当数组里有大量元素等于 pivot 时，这些元素可能被分散到左右两边，后续递归还会继续处理它们。

重复元素多时，真正应该做的是把等于 pivot 的元素一次性排除出递归。

2. 三路划分的三个区域

三路快排把数组分成：

区域	含义
`< pivot`	小于基准
`== pivot`	等于基准
`> pivot`	大于基准

中间等于 pivot 的区域已经处于正确位置，不需要再递归。

3. 指针 lt、i、gt 分别做什么

常见实现维护三个指针：

lt: 小于区右边界
i: 当前扫描位置
gt: 大于区左边界

初始：

lt = left
i = left
gt = right

扫描结束后，[lt, gt] 就是等于 pivot 的区域。

4. 三种情况如何处理

伪代码如下：

while i <= gt:
  if nums[i] < pivot:
    swap(nums[i], nums[lt])
    lt++
    i++
  else if nums[i] > pivot:
    swap(nums[i], nums[gt])
    gt--
  else:
    i++

注意 nums[i] > pivot 时，交换过来的元素还没检查，所以 i 不能加。

5. 为什么等于区不用递归

等于 pivot 的元素彼此之间顺序无所谓，因为它们值相同。

并且它们左边都小于 pivot，右边都大于 pivot，所以中间区域已经在最终排序中的正确位置范围。

后续只需要递归：

[left, lt - 1]
[gt + 1, right]

6. 复杂度怎么理解

在大量重复元素场景中，三路快排能显著减少递归规模。

例如数组中所有元素都相同：

普通快排可能仍然不断划分；
三路快排一次扫描后，等于区覆盖整个数组，递归直接结束。

情况	三路快排表现
全部相同	一趟扫描
重复很多	递归层数减少
元素互异	接近普通快排

7. 和荷兰国旗问题的关系

三路快排的 partition 和荷兰国旗问题很像。

荷兰国旗问题把 0、1、2 分成三段；三路快排把 < pivot、== pivot、> pivot 分成三段。

所以理解三路快排时，可以把 pivot 看成中间颜色。

8. 常见误区与追问

误区：三路快排只适合三个取值的数组。 它适合任意数组，只是按 pivot 分成三类关系。
误区：交换大于 pivot 的元素后 i 也要加。 不能加，因为从右边换来的元素还没检查。
误区：等于 pivot 的区域还需要递归排序。 该区域元素值相同，不需要处理。
追问：什么时候三路快排优势最大？ 数组中重复元素很多时优势最明显。
追问：它和荷兰国旗有什么关系？ 两者都使用三路划分思想。

简化版

详细版