PHP8.0百题实战：PHP实现快速排序非递归版本-php教程-PHP中文网

PHP 8.0中非递归快排用栈模拟递归，避免栈溢出，空间复杂度稳定为O(log n)；核心是压入[left, right]区间，partition分区后按需入栈子区间，支持升序原地排序。

php8.0百题实战：php实现快速排序非递归版本

PHP 8.0 中实现快速排序的非递归版本，核心是用栈模拟递归调用过程，避免函数栈溢出风险，尤其适合大数据量或深度受限环境。它不依赖系统调用栈，逻辑清晰、可控性强。

为什么需要非递归快排

递归快排在最坏情况下（如已排序数组）递归深度达 O(n)，易触发 PHP 的 max_execution_time 或栈溢出；非递归版将待处理区间压入栈中，每次弹出一个子区间进行划分，空间复杂度稳定为 O(log n)（理想情况）或 O(n)（最坏），但可显式控制。

关键步骤与栈结构设计

使用 PHP 数组模拟栈，每个元素为 [left, right] 索引对，表示当前需排序的闭区间：

初始将整个数组区间 [0, count($arr) - 1] 入栈
循环直到栈空：弹出一个区间，对该区间做一次 partition（分区）操作
若左子区间长度 > 1，将其入栈；同理处理右子区间
partition 函数返回基准元素最终位置，用于划分左右

完整可运行代码（PHP 8.0+）

注意：此实现为升序，原地排序，保持键值关联不适用（仅适用于索引数组）

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

function quickSortIterative(array $arr): array
{
    if (count($arr) // 拷贝数组，避免引用修改原数组
$result = $arr;
$stack = [[0, count($arr) - 1]];

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

    if ($left >= $right) {
        continue;
    }

    // 分区操作：返回基准索引
    $pivotIndex = partition($result, $left, $right);

    // 先压右区间（后处理），再压左区间（先处理），模拟递归顺序（可选）
    if ($pivotIndex + 1 <p>}</p><p>function partition(array &$arr, int $low, int $high): int
{
$pivot = $arr[$high]; // 取末尾为基准
$i = $low - 1;</p><pre class="brush:php;toolbar:false;">for ($j = $low; $j <p>}</p><p>// 测试
$test = [64, 34, 25, 12, 22, 11, 90, 5];
var_dump(quickSortIterative($test));
// 输出：[5, 11, 12, 22, 25, 34, 64, 90]
</p>