三路快排 3-way Quicksort

交换排序 · 快排变体 · 荷兰国旗划分

普通快排的软肋

普通快排每趟只把数组分成「< pivot」和「≥ pivot」两段，pivot 自己归位。可一旦数组里有大量重复元素，等于 pivot 的那些值会被反复塞进同一侧、一遍遍参与后续划分——递归变深，最坏退化到 O(n²)。极端情况「全部相等」时，普通快排慢得离谱。

三路快排怎么做（荷兰国旗划分）

三路快排把一趟划分从「两段」升级成三段：< pivot / == pivot / > pivot。等于 pivot 的元素一次性集中到中段、立即钉死，再也不参与递归——重复元素越多，省得越狠。这个「把一组数按某个基准劈成三段」的过程，就是经典的荷兰国旗问题（Dutch National Flag）。

做法是三个指针 lt / i / gt：lt 是「小于区」的右边界、gt 是「大于区」的左边界、i 是扫描游标。扫描时看 a[i] 和 pivot 的关系——小于就和 lt 交换、lt 与 i 同时右移；大于就和 gt 交换、gt 左移（i 不动，因为换过来的值还没查过）；等于就只把 i 右移、留在中段。当 i 越过 gt，三段就分好了。

下面固定 8 个数 [5, 3, 8, 3, 5, 8, 3, 5]（只有 3、5、8 三种值、大量重复）。点「下一步」看首趟划分（pivot=5）怎么把它们一趟分成 [3,3,3 | 5,5,5 | 8,8]——中间那段 5 直接钉死、不再递归，只剩左右两小段要处理。右侧区间栈显示「还有哪些段待划分」。

复杂度与适用

和普通快排一样，平均 O(n log n)、原地、不稳定。但在有大量重复键的数据上，三路快排把「等于 pivot」的元素一次清掉，递归规模骤减——重复种类越少越接近 O(n)。所以它是处理「键的取值范围小、重复多」场景的利器（如按枚举字段、评分、类别排序）。

想先复习普通快排的「基准 + 区间栈」是怎么回事，可回看快速排序页——三路快排正是在它基础上，把划分从两段改成三段。