php实现快速排序

快速排序原理

快速排序是一种分治算法，通过选择一个基准元素将数组分成两部分，一部分小于基准，另一部分大于基准，递归地对子数组进行排序。其平均时间复杂度为O(n log n)，最坏情况下为O(n²)。

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));
}

代码说明

基准元素选择数组第一个元素$array[0]。遍历剩余元素，小于基准的放入$left数组，大于等于的放入$right数组。递归调用quickSort处理子数组，最后合并结果。

优化建议

对于大数组，随机选择基准元素可避免最坏情况：

$pivotIndex = array_rand($array);
$pivot = $array[$pivotIndex];

使用示例

$unsorted = [3, 0, 2, 5, -1, 4, 1];
$sorted = quickSort($unsorted);
print_r($sorted); // 输出 [-1, 0, 1, 2, 3, 4, 5]