PHP 8.0中非递归快排用栈模拟递归，避免栈溢出，空间复杂度稳定为O(log n)；核心是压入[left, right]区间，partition分区后按需入栈子区间，支持升序原地排序。
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+）
注意：此实现为升序，原地排序，保持键值关联不适用（仅适用于索引数组）
立即学习“PHP免费学习笔记（深入）”；
function quickSortIterative(array $arr): array
{
if (count($arr) <= 1) {
return $arr;
}
<pre class="brush:php;toolbar:false;">// 拷贝数组，避免引用修改原数组
$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 < $right) {
$stack[] = [$pivotIndex + 1, $right];
}
if ($left < $pivotIndex - 1) {
$stack[] = [$left, $pivotIndex - 1];
}
}
return $result;}
function partition(array &$arr, int $low, int $high): int { $pivot = $arr[$high]; // 取末尾为基准 $i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($arr[$j] <= $pivot) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]]; // PHP 8.0+ 结构化赋值
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;}
// 测试 $test = [64, 34, 25, 12, 22, 11, 90, 5]; var_dump(quickSortIterative($test)); // 输出：[5, 11, 12, 22, 25, 34, 64, 90]
注意事项与优化点
- PHP 8.0 支持解构赋值（
[$a, $b] = [$b, $a]），比传统临时变量更简洁安全 - 为防最坏性能，可改用三数取中法选基准，但会增加常数开销
- 小数组（如长度
- 该版本不保留原始键名，如需排序关联数组，请改用
uasort或手动维护索引映射
