php实现快速排序

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

代码说明

1. 基线条件：当数组长度小于等于1时直接返回，因为单个元素已经是有序的。
2. 选择基准值：通常选择第一个元素作为基准值（pivot）。
3. 分区操作：将剩余元素与基准值比较，分为小于基准值的左数组和大于等于基准值的右数组。
4. 递归排序：对左右子数组递归调用快速排序函数。
5. 合并结果：将排序后的左数组、基准值和右数组合并。

优化版本

以下是原地排序的优化版本，减少内存使用：

function quickSortOptimized(array &$array, int $left = 0, int $right = null): void {
    if ($right === null) {
        $right = count($array) - 1;
    }

    if ($left >= $right) {
        return;
    }

    $pivotIndex = partition($array, $left, $right);
    quickSortOptimized($array, $left, $pivotIndex - 1);
    quickSortOptimized($array, $pivotIndex + 1, $right);
}

function partition(array &$array, int $left, int $right): int {
    $pivot = $array[$right];
    $i = $left;

    for ($j = $left; $j < $right; $j++) {
        if ($array[$j] < $pivot) {
            [$array[$i], $array[$j]] = [$array[$j], $array[$i]];
            $i++;
        }
    }

    [$array[$i], $array[$right]] = [$array[$right], $array[$i]];
    return $i;
}

使用示例

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

// 优化版本使用
$array = [3, 6, 8, 10, 1, 2, 1];
quickSortOptimized($array);
print_r($array);

性能分析

1. 时间复杂度：平均情况O(n log n)，最坏情况O(n²)。
2. 空间复杂度：原始版本O(n)，优化版本O(log n)。
3. 稳定性：快速排序是不稳定的排序算法。