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，最终合并结果为左数组 + 基准 + 右数组。
优化建议
-
随机基准：避免最坏情况（如已排序数组），可随机选择基准：
$pivotIndex = rand(0, count($array) - 1); $pivot = $array[$pivotIndex]; -
三数取中法：选择首、中、尾元素的中位数作为基准：
$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]
