三路快速排序（3-Way Quicksort） 题目描述：给定一个可能包含重复元素的整数数组，请你使用三路快速排序算法对数组进行原地升序排序。该算法应高效处理大量重复元素的情况，避免普通快速排序在重复元素多时性能退化到O(n²)的问题。 解题过程： 核心思想分析 普通快速排序每次将数组划分为"小于基准"和"大于等于基准"两部分，当重复元素多时，大量相等元素会集中到一侧分区，导致分区不平衡。三路快速排序通过将数组分为三部分来解决这个问题： 小于基准值的元素（ < pivot） 等于基准值的元素（= pivot） 大于基准值的元素（> pivot） 指针定义 我们需要三个指针来标记三个区域的边界： low ：指向数组起始位置 high ：指向数组末尾位置 i ：当前遍历的指针，从low开始向右移动 lt （less than）：指向小于区的末尾，保证[ low, lt ]区间都小于基准 gt （greater than）：指向大于区的起始，保证[ gt, high ]区间都大于基准 基准选择 选择数组第一个元素作为基准值： pivot = arr[low] 分区过程详解 初始化： i = low + 1 , lt = low , gt = high 遍历过程（当i ≤ gt时）： 情况1：如果arr[ i] < pivot 交换arr[ i]和arr[ lt+1 ] i右移，lt右移 这样小于区的范围扩大了 情况2：如果arr[ i ] > pivot 交换arr[ i]和arr[ gt ] gt左移（i不移动，因为交换过来的新元素还需要检查） 情况3：如果arr[ i ] == pivot i右移，保持相等区在中间 具体示例演示 对数组[ 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 ]进行排序： 初始：pivot=3, i=1, lt=0, gt=9 arr[ 1]=1<3：交换arr[ 1]和arr[ 1]，i=2, lt=1 → [ 3,1,... ] arr[ 2]=4>3：交换arr[ 2]和arr[ 9]，gt=8 → [ 3,1,3,...5,4 ] arr[ 2 ]=3=3：i右移 → i=3 继续此过程直到i>gt 递归处理 分区完成后，数组分为三部分： [ low, lt ]：小于pivot，需要递归排序 [ lt+1, gt-1 ]：等于pivot，已有序 [ gt, high ]：大于pivot，需要递归排序 算法优势 大量重复元素时，相等元素直接归到中间区，不再参与后续递归 时间复杂度从普通快排的O(n²)优化到O(n)（大量重复时） 平均情况仍保持O(n log n) 实现要点 注意边界条件：当子数组长度≤1时直接返回 交换操作要确保指针正确移动 递归调用时排除已有序的相等区间 通过这种三路分区策略，算法能够高效处理包含大量重复元素的排序场景，是实际工程中常用的优化版本。