PHP8.3快速排序随机基准值怎么写-php教程-PHP中文网

PHP 8.3 中快速排序采用 random_int() 随机选取 pivot 并交换至末尾，再执行 Lomuto 分区，避免最坏 O(n²) 时间复杂度；代码支持严格模式与多种可比较类型。

php8.3快速排序随机基准值怎么写

PHP 8.3 中实现快速排序并使用随机基准值（pivot），核心是避免最坏情况（如已排序数组导致 O(n²)），关键是每次递归前用 random_int() 在子数组范围内选一个随机索引作为 pivot，再将其与末尾（或开头）元素交换，再按常规分区逻辑处理。

1. 随机 pivot 的安全选取方式

PHP 8.3 推荐使用 random_int($min, $max)（加密安全、无偏移），替代过时的 rand() 或 mt_rand()。注意边界必须有效，且交换后要确保 pivot 参与分区。

在 partition() 开头生成随机索引：$randIdx = random_int($low, $high);
立即将该位置元素与 $arr[$high] 交换，使 pivot 落在末尾，复用经典 Lomuto 分区逻辑
不推荐“直接取 $arr[random_int()] 值比较”，因为重复值多时无法保证分区稳定性，且难追踪索引

2. 完整可运行示例（Lomuto 分区 + 随机 pivot）

以下代码兼容 PHP 8.3，含类型声明、严格模式友好，支持整数/字符串等可比较类型：

PHP

编写健壮的PHP代码，规避类型转换陷阱、数组怪癖及常见安全漏洞。

下载

function quickSort(array $arr, int $low = 0, int $high = null): array
{
    if ($high === null) {
        $high = count($arr) - 1;
    }
    if ($low function partition(array &$arr, int $low, int $high): int
{
// ✅ 随机选索引，并与末尾交换
$randIdx = random_int($low, $high);
[$arr[$randIdx], $arr[$high]] = [$arr[$high], $arr[$randIdx]];<pre class="brush:php;toolbar:false;">$pivot = $arr[$high];
$i = $low - 1;

for ($j = $low; $j <p>}</p><p>// 使用示例
$nums = [64, 34, 25, 12, 22, 11, 90];
$sorted = quickSort($nums);
print_r($sorted); // [11, 12, 22, 25, 34, 64, 90]
</p>

3. 注意事项（PHP 8.3 特别提醒）

random_int() 在 PHP 7.0+ 引入，8.3 中完全可靠；若运行环境禁用 CSPRNG（极罕见），会抛出 Exception，建议包裹 try-catch（生产环境可加降级逻辑）
原地排序需传引用（&$arr），但顶层函数返回新数组更符合函数式习惯；如需真正原地，去掉返回值，只操作传入数组引用
对空数组或单元素数组，递归终止条件 $low 已覆盖，无需额外判断
PHP 8.3 的 JIT 和类型推导对此类算法优化有限，性能关键场景建议配合 array_values() 确保索引连续，避免稀疏数组拖慢