php使用递归与迭代实现快速排序示例

在PHP中，快速排序是一种高效的排序算法，它使用分而治之的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。以下分别使用递归和迭代（使用栈来模拟递归过程）来实现快速排序的示例。

### 递归实现快速排序

function quickSortRecursive(&$arr, $left = 0, $right = null) {
    if ($right === null) {
        $right = count($arr) - 1;
    }
    if ($left < $right) {
        $pivotIndex = partition($arr, $left, $right);
        quickSortRecursive($arr, $left, $pivotIndex - 1);
        quickSortRecursive($arr, $pivotIndex + 1, $right);
    }
}

function partition(&$arr, $left, $right) {
    $pivot = $arr[$right];
    $i = $left - 1;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换 $arr[$i] 和 $arr[$j]
            list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]);
        }
    }
    // 交换 $arr[$i+1] 和 $arr[$right]
    list($arr[$i + 1], $arr[$right]) = array($arr[$right], $arr[$i + 1]);
    return $i + 1;
}

// 示例
$arr = [10, 7, 8, 9, 1, 5];
quickSortRecursive($arr);
print_r($arr);

### 迭代实现快速排序（使用栈）

迭代实现稍微复杂一些，因为我们需要手动管理递归栈。

function quickSortIterative(&$arr) {
    $stack = [];
    $left = 0;
    $right = count($arr) - 1;
    
    array_push($stack, $left);
    array_push($stack, $right);
    
    while (!empty($stack)) {
        $right = array_pop($stack);
        $left = array_pop($stack);
        
        if ($left < $right) {
            $pivotIndex = partition($arr, $left, $right);
            
            if ($pivotIndex - 1 > $left) {
                array_push($stack, $left);
                array_push($stack, $pivotIndex - 1);
            }
            
            if ($pivotIndex + 1 < $right) {
                array_push($stack, $pivotIndex + 1);
                array_push($stack, $right);
            }
        }
    }
}

// partition 函数与上面递归实现中的相同

// 示例
$arr = [10, 7, 8, 9, 1, 5];
quickSortIterative($arr);
print_r($arr);

以上两种实现均展示了如何在PHP中使用快速排序算法。递归版本更加直观易懂，而迭代版本则通过手动管理栈来模拟递归过程，避免了递归可能带来的栈溢出问题（尽管在大多数现代编程语言中，递归栈的深度都足够大，以至于在实际应用中很少会遇到栈溢出的问题）。