三路划分快速排序将数组分为小于、等于、大于基准的三部分，用$lt、$gt、$i三指针维护边界，一次划分即归集所有重复元素，避免传统快排在重复数据下退化为O(n²)，PHP 8.3中通过解构赋值和引用传参高效实现。
PHP 8.3 中实现快速排序的三路划分（Dutch National Flag Partition），核心是将数组分为 小于、等于、大于 基准值（pivot）的三个区间，特别适合含大量重复元素的场景，可避免传统快排在重复数据下的退化问题。
三路划分原理与关键指针
用三个指针维护区间边界：
-
$lt：指向「小于 pivot」区域的右边界（初始为
$left - 1） -
$gt：指向「大于 pivot」区域的左边界（初始为
$right + 1） -
$i：当前遍历位置（初始为
$left），范围在[$lt+1, $gt-1]
循环中根据 $arr[$i] 与 pivot 比较，决定交换并移动对应指针。
完整可运行的递归实现
以下代码兼容 PHP 8.3，使用严格类型提示和引用传参，避免复制大数组：
function quickSort3Way(array &$arr, int $left = 0, int $right = null): void
{
if ($right === null) {
$right = count($arr) - 1;
}
if ($left >= $right) {
return;
}
<pre class="brush:php;toolbar:false;">$pivot = $arr[$left];
$lt = $left - 1;
$gt = $right + 1;
$i = $left;
while ($i $pivot) {
$gt--;
[$arr[$i], $arr[$gt]] = [$arr[$gt], $arr[$i]];
// 注意：此处不增加 $i，因为 $arr[$i] 是刚换过来的未知值
} else {
$i++;
}
}
// 递归处理小于区和大于区
quickSort3Way($arr, $left, $lt);
quickSort3Way($arr, $gt, $right);}
调用示例：
$data = [3, 6, 8, 3, 1, 3, 9, 3, 2]; quickSort3Way($data); print_r($data); // [1,2,3,3,3,3,6,8,9]
为什么比普通快排更稳？
三路划分直接跳过所有等于 pivot 的元素，递归深度不再依赖重复值数量：
- 普通快排对
[3,3,3,...,3]会退化为 O(n²)，每次只减少一个元素 - 三路划分一次就把全部 3 归入中间段，后续仅递归空区间或极小区间
- PHP 8.3 的解构赋值
[$a,$b] = [$b,$a]让交换更简洁安全
实际使用注意事项
该实现已适配 PHP 8.3 特性，但需注意：
- 务必用 引用传参（
&$arr），否则排序无效 - 基准选
$arr[$left]简单高效；若担心最坏情况，可用三数取中优化 pivot 选择 - 小数组（如长度
- PHP 内置
sort()已高度优化，生产环境优先用内置函数；此实现适用于教学、定制需求或学习算法原理
php免费学习视频：立即使用
踏上前端学习之旅，开启通往精通之路！从前端基础到项目实战，循序渐进，一步一个脚印，迈向巅峰！
