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

代码说明

基准元素选择数组第一个元素$array[0]，遍历剩余元素将其分配到左右两个子数组。递归调用quickSort处理子数组，最后合并左数组、基准元素和右数组。

优化建议

对于大型数组，可采用随机选择基准或三数取中法优化性能。PHP的usort函数内部也使用快速排序，可直接调用：

usort($array, function($a, $b) {
    return $a <=> $b;
});

时间复杂度

平均时间复杂度为O(n log n)，最坏情况（如已排序数组）会退化到O(n²)。空间复杂度为O(log n)因递归调用栈。