PHP8.3快速排序LeetCode怎么过-php教程-PHP中文网

php 8.3 过 leetcode 快排题需三数取中或随机选 pivot 避免最坏递归深度，必须原地分区+尾递归优化降低栈深，禁用新建数组拼接，且不可用 sort() 等禁用函数。

php8.3快速排序leetcode怎么过

PHP 8.3 过 LeetCode 的快速排序题（比如 912. 排序数组 或 215. 数组中的第 K 个最大元素），关键不是“重写快排”，而是用对策略、避开陷阱、符合平台约束。LeetCode 对 PHP 提交有明确限制：不能超时（TLE）、不能爆栈（RE）、不能用禁用函数（如 sort() 在某些题会判作弊），且 PHP 8.3 默认启用严格类型和 JIT，对递归深度和内存更敏感。

一、基础快排必须加三数取中或随机 pivot

LeetCode 测试用例包含大量极端情况：全相同元素、已升序/降序数组。若固定选首/尾为 pivot，PHP 8.3 下递归深度可能达 O(n)，直接触发 Fatal error: Maximum function nesting level 或超时。

改用 rand($low, $high) 随机选 pivot，并交换到末尾再分区
或更稳妥：三数取中（取 $low、mid、$high 三位置的中位数）
PHP 8.3 注意：rand() 在 srand() 未显式调用时仍可用，但建议加 mt_srand() 提升随机性

二、必须用原地分区 + 尾递归优化

LeetCode 不接受新建数组拼接（如 array_merge($left, [$pivot], $right)），既浪费空间又易超内存。PHP 8.3 中递归过深还会被 JIT 拦截。

PHP

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

下载

使用双指针原地分区（Lomuto 或 Hoare 方式），只操作索引，不新建子数组
递归调用前，先处理较小子数组，再用循环处理较大子数组（模拟尾递归），降低栈深度
示例节选（Lomuto 分区 + 尾递归优化）：

function quickSort(&$nums, $low = 0, $high = null) {
  if ($high === null) $high = count($nums) - 1;
  if ($low >= $high) return;

  // 随机 pivot
  $randIdx = mt_rand($low, $high);
  [$nums[$randIdx], $nums[$high]] = [$nums[$high], $nums[$randIdx]];

  $pivotIdx = partition($nums, $low, $high);

  // 尾递归优化：先递归小半边，大半边用 while 循环
  if ($pivotIdx - $low     quickSort($nums, $low, $pivotIdx - 1);
    $low = $pivotIdx + 1;
  } else {
    quickSort($nums, $pivotIdx + 1, $high);
    $high = $pivotIdx - 1;
  }
  while ($low     quickSort($nums, $low, $high); // 实际应展开为迭代逻辑，此处简写示意
    break;
  }
}