PHP 快速排序算法
最后修改于 2025 年 4 月 16 日
基本定义
一个算法是解决问题的逐步过程。在编程中，算法被实现为函数或方法。
排序意味着将数据按特定顺序排列，通常是升序或降序。高效的排序对于许多应用程序至关重要。
常见的排序算法包括
- 快速排序
- 归并排序
- 气泡排序
- 插入排序
- 选择排序
- 堆排序
快速排序概述
快速排序是一种分治算法。它通过选择一个“枢轴”元素并将数组围绕该枢轴进行分区来工作。它具有 O(n log n) 的平均时间复杂度，这使得它对大型数据集非常有效。
基本快速排序实现
这是一个用 PHP 对数字数据进行快速排序的基本实现
quick_sort_basic.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)
);
}
$numbers = [3, 6, 8, 10, 1, 2, 1];
$sorted = quickSort($numbers);
print_r($sorted); // Outputs: [1, 1, 2, 3, 6, 8, 10]
此实现通过将元素分区为左（小于枢轴）和右（大于枢轴）子数组来递归地对数组进行排序。
对文本数据进行排序
快速排序也可以按字母顺序对字符串进行排序。这里有一个例子
quick_sort_strings.php
<?php
function quickSortStrings(array $array): array {
if (count($array) <= 1) {
return $array;
}
$pivot = $array[0];
$left = $right = [];
for ($i = 1; $i < count($array); $i++) {
if (strcmp($array[$i], $pivot) < 0) {
$left[] = $array[$i];
} else {
$right[] = $array[$i];
}
}
return array_merge(
quickSortStrings($left),
[$pivot],
quickSortStrings($right)
);
}
$names = ["John", "Alice", "Bob", "Eve", "Charlie"];
$sortedNames = quickSortStrings($names);
print_r($sortedNames); // Outputs: ["Alice", "Bob", "Charlie", "Eve", "John"]
此版本使用 strcmp 来比较字符串。该算法的工作方式与数字相同，只是使用了不同的比较逻辑。
降序排序
要按降序排序，我们只需反转比较逻辑
quick_sort_descending.php
<?php
function quickSortDesc(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(
quickSortDesc($left),
[$pivot],
quickSortDesc($right)
);
}
$numbers = [3, 6, 8, 10, 1, 2, 1];
$sortedDesc = quickSortDesc($numbers);
print_r($sortedDesc); // Outputs: [10, 8, 6, 3, 2, 1, 1]
唯一的改变是将比较运算符从 < 更改为 >。这会将较大的元素放入左侧数组，从而产生降序。
优化快速排序
基本实现可以通过使用原地分区和随机枢轴选择来进行优化
quick_sort_optimized.php
<?php
function quickSortOptimized(array &$array, int $low, int $high): void {
if ($low < $high) {
$pi = partition($array, $low, $high);
quickSortOptimized($array, $low, $pi - 1);
quickSortOptimized($array, $pi + 1, $high);
}
}
function partition(array &$array, int $low, int $high): int {
$pivot = $array[$high];
$i = $low - 1;
for ($j = $low; $j <= $high - 1; $j++) {
if ($array[$j] < $pivot) {
$i++;
[$array[$i], $array[$j]] = [$array[$j], $array[$i]];
}
}
[$array[$i + 1], $array[$high]] = [$array[$high], $array[$i + 1]];
return $i + 1;
}
$numbers = [3, 6, 8, 10, 1, 2, 1];
quickSortOptimized($numbers, 0, count($numbers) - 1);
print_r($numbers); // Outputs: [1, 1, 2, 3, 6, 8, 10]
此版本原地排序，不创建新数组，从而减少内存使用。它还使用最后一个元素作为枢轴，可以将其随机化，以便在近乎排序的数据上获得更好的性能。
快速排序与插入排序基准测试
让我们将快速排序与插入排序进行比较，看看性能差异
sort_benchmark.php
<?php
function insertionSort(array $array): array {
for ($i = 1; $i < count($array); $i++) {
$key = $array[$i];
$j = $i - 1;
while ($j >= 0 && $array[$j] > $key) {
$array[$j + 1] = $array[$j];
$j--;
}
$array[$j + 1] = $key;
}
return $array;
}
// Generate large array
$largeArray = [];
for ($i = 0; $i < 10000; $i++) {
$largeArray[] = rand(1, 100000);
}
// Quick Sort benchmark
$start = microtime(true);
quickSortOptimized($largeArray, 0, count($largeArray) - 1);
$quickTime = microtime(true) - $start;
// Insertion Sort benchmark
$start = microtime(true);
insertionSort($largeArray);
$insertionTime = microtime(true) - $start;
echo "Quick Sort time: " . number_format($quickTime, 5) . " seconds\n";
echo "Insertion Sort time: " . number_format($insertionTime, 5) . " seconds\n";
在具有 10,000 个元素的典型机器上，您将看到类似的结果
Quick Sort time: 0.01234 seconds Insertion Sort time: 1.23456 seconds
对于大型数据集，快速排序明显更快，因为它具有 O(n log n) 的平均时间复杂度，而插入排序的复杂度为 O(n²)。
何时使用快速排序
- 大型数据集： 快速排序在大型集合中表现出色。
- 平均情况性能： 当 O(n log n) 可以接受时。
- 内存限制： 原地版本使用最少的内存。
何时避免快速排序
- 近乎排序的数据： 如果没有优化，可能会降低到 O(n²)。
- 需要稳定性： 快速排序不是一个稳定的排序算法。
- 小型数据集： 更简单的算法可能更有效。
来源
本教程介绍了 PHP 中的快速排序算法，并提供了数字和文本数据的示例，包括与插入排序的性能比较。
作者
列出 所有 PHP 教程。