php实现快速排序

快速排序原理

快速排序是一种分治算法，通过选取一个基准元素将数组分为两部分，一部分小于基准，另一部分大于基准，递归地对子数组进行排序。

PHP实现代码

function quickSort(array $array): array {
    if (count($array) <= 1) {
        return $array;
    }

    $pivot = $array[0];
    $left = $right = [];

    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }

    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

代码说明

• 基准元素选择：默认使用数组第一个元素作为基准（$pivot）。
• 分区操作：遍历剩余元素，将小于基准的放入$left数组，大于等于的放入$right数组。
• 递归合并：对左右子数组递归调用quickSort，最终合并结果为左数组 + 基准 + 右数组。

优化建议

1. 随机基准：避免最坏情况（如已排序数组），可随机选择基准：

   

   $pivotIndex = rand(0, count($array) - 1);
   $pivot = $array[$pivotIndex];

2. 三数取中法：选择首、中、尾元素的中位数作为基准：

   $mid = floor(count($array) / 2);
   $pivot = median($array[0], $array[$mid], $array[count($array) - 1]);

时间复杂度

• 平均情况：O(n log n)
• 最坏情况（基准选择不佳）：O(n²)
• 空间复杂度：O(log n)（递归栈）

使用示例

$unsorted = [3, 6, 8, 10, 1, 2, 1];
$sorted = quickSort($unsorted);
print_r($sorted); // 输出: [1, 1, 2, 3, 6, 8, 10]