PHP8.4快速排序非递归怎么写-php教程-PHP中文网

PHP 8.4 中可用数组模拟栈实现非递归快速排序，避免栈溢出；核心是用 $stack 存储待排区间，循环执行 Lomuto 分区并压入子区间，支持整数/字符串原地排序。

php8.4快速排序非递归怎么写

PHP 8.4 中实现快速排序的非递归版本，核心是用栈（数组模拟）替代函数调用栈，避免递归深度限制和栈溢出风险。它比递归版稍复杂，但更可控、更适合大数据量或深度受限环境。

用数组模拟栈管理待排序区间

每次把待处理的 [left, right] 区间入栈；循环出栈，对当前区间做一次 partition 分割，再将产生的两个子区间（如果长度 > 1）压入栈中。

PHP 中直接用 $stack = [] 和 array_push()/array_pop() 模拟栈（LIFO）
每个栈元素是关联数组，如 ['left' => 0, 'right' => 9]，语义清晰不易错
注意边界判断：仅当 $left 才处理，单元素或空区间跳过

partition 分区逻辑保持不变（Lomuto 或 Hoare 均可）

非递归只改控制流，不改排序本质。推荐用经典的 Lomuto 方式（基准选末尾，一趟划分出左右两部分）：

PHP

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

下载

取 $pivot = $arr[$right]
用 $i 记录小于等于 pivot 的最右位置，遍历 $j 从 $left 到 $right - 1
若 $arr[$j] ，交换 <code>$arr[++$i] 和 $arr[$j]
最后交换 $arr[$i + 1] 和 $arr[$right]，返回新基准位置

完整可运行示例（PHP 8.4 兼容）

以下代码已在 PHP 8.4 下验证，支持整数/字符串数组，原地排序：

function quickSortIterative(array &$arr): void
{
    $n = count($arr);
    if ($n $stack = [['left' => 0, 'right' => $n - 1]];

while (!empty($stack)) {
    $range = array_pop($stack);
    $left  = $range['left'];
    $right = $range['right'];

    if ($left >= $right) continue;

    // Partition: Lomuto scheme
    $pivotIndex = $right;
    $pivot = $arr[$pivotIndex];
    $i = $left - 1;

    for ($j = $left; $j  $i + 1, 'right' => $right]);
    }
    if ($left  $left, 'right' => $i - 1]);
    }
}

}

// 使用示例 $nums = [64, 34, 25, 12, 22, 11, 90]; quickSortIterative($nums); print_r($nums); // [11, 12, 22, 25, 34, 64, 90]