PHP 归并排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法 是一种逐步解决问题或执行计算的程序。在编程中，算法被实现为函数或方法。
排序 是指将数据按特定顺序排列，通常是升序或降序。有效的排序对于优化其他算法（如搜索操作）至关重要。
常见的排序算法包括
- 归并排序
- 快速排序
- 气泡排序
- 插入排序
- 选择排序
- 堆排序
归并排序概述
归并排序是一种分治算法，它递归地将输入数组分成两半，对它们进行排序，然后合并已排序的两半。
它在所有情况下都具有 O(n log n) 的时间复杂度，使其对于大型数据集非常有效。它是一种稳定的排序算法，需要 O(n) 的额外空间。
基本归并排序实现
以下是升序排列数字数据的基本归并排序实现。
merge_sort_basic.php
<?php
function mergeSort(array $array): array {
if (count($array) <= 1) {
return $array;
}
$mid = (int) (count($array) / 2);
$left = array_slice($array, 0, $mid);
$right = array_slice($array, $mid);
$left = mergeSort($left);
$right = mergeSort($right);
return merge($left, $right);
}
function merge(array $left, array $right): array {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] <= $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
$numbers = [34, 7, 23, 32, 5, 62];
$sorted = mergeSort($numbers);
print_r($sorted);
此实现递归地分割数组，直到每个子数组只有一个元素，然后按排序顺序将它们合并回原数组。
对文本数据进行排序
归并排序也可以按字母顺序对字符串进行排序。这是一个包含文本数据的示例。
merge_sort_text.php
<?php
function mergeSortText(array $array): array {
if (count($array) <= 1) {
return $array;
}
$mid = (int) (count($array) / 2);
$left = array_slice($array, 0, $mid);
$right = array_slice($array, $mid);
$left = mergeSortText($left);
$right = mergeSortText($right);
return mergeText($left, $right);
}
function mergeText(array $left, array $right): array {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if (strcmp($left[$i], $right[$j]) <= 0) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
$names = ["John", "Alice", "Bob", "Zoe", "Charlie"];
$sortedNames = mergeSortText($names);
print_r($sortedNames);
此版本使用 strcmp 比较字符串。输出将是按字母顺序排列的名称。
降序排序
要以降序排序，我们只需在合并函数中反转比较。
merge_sort_desc.php
<?php
function mergeSortDesc(array $array): array {
if (count($array) <= 1) {
return $array;
}
$mid = (int) (count($array) / 2);
$left = array_slice($array, 0, $mid);
$right = array_slice($array, $mid);
$left = mergeSortDesc($left);
$right = mergeSortDesc($right);
return mergeDesc($left, $right);
}
function mergeDesc(array $left, array $right): array {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] >= $right[$j]) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
$numbers = [34, 7, 23, 32, 5, 62];
$sortedDesc = mergeSortDesc($numbers);
print_r($sortedDesc);
唯一的更改是合并函数中的比较运算符，它现在检查大于或等于而不是小于或等于。
带有回调的通用归并排序
我们可以通过添加比较回调使我们的归并排序更灵活。
merge_sort_generic.php
<?php
function mergeSortGeneric(array $array, callable $compare): array {
if (count($array) <= 1) {
return $array;
}
$mid = (int) (count($array) / 2);
$left = array_slice($array, 0, $mid);
$right = array_slice($array, $mid);
$left = mergeSortGeneric($left, $compare);
$right = mergeSortGeneric($right, $compare);
return mergeGeneric($left, $right, $compare);
}
function mergeGeneric(array $left, array $right, callable $compare): array {
$result = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($compare($left[$i], $right[$j]) <= 0) {
$result[] = $left[$i++];
} else {
$result[] = $right[$j++];
}
}
while ($i < count($left)) {
$result[] = $left[$i++];
}
while ($j < count($right)) {
$result[] = $right[$j++];
}
return $result;
}
// Ascending sort
$ascCompare = fn($a, $b) => $a <=> $b;
$numbers = [34, 7, 23, 32, 5, 62];
$sortedAsc = mergeSortGeneric($numbers, $ascCompare);
print_r($sortedAsc);
// Descending sort
$descCompare = fn($a, $b) => $b <=> $a;
$sortedDesc = mergeSortGeneric($numbers, $descCompare);
print_r($sortedDesc);
此版本接受一个比较函数，使其适用于任何数据类型和排序顺序。太空船运算符 (<=>) 简化了比较逻辑。
归并排序与快速排序基准测试
让我们比较一下归并排序和快速排序在大型数据集上的性能。
sort_benchmark.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));
}
function generateRandomArray(int $size): array {
$array = range(1, $size);
shuffle($array);
return $array;
}
$largeArray = generateRandomArray(10000);
// Merge sort benchmark
$start = microtime(true);
$mergeSorted = mergeSort($largeArray);
$mergeTime = microtime(true) - $start;
// Quick sort benchmark
$start = microtime(true);
$quickSorted = quickSort($largeArray);
$quickTime = microtime(true) - $start;
echo "Merge Sort time: " . number_format($mergeTime, 6) . " seconds\n";
echo "Quick Sort time: " . number_format($quickTime, 6) . " seconds\n";
两种算法的平均时间复杂度都为 O(n log n)，但快速排序通常在实践中更快，因为它具有更好的缓存性能和更少的内存使用。但是，归并排序是稳定的，并保证 O(n log n) 的性能。
何时使用归并排序
- 需要稳定性： 当相等元素必须保留顺序时
- 外部排序： 当数据不适合内存时
- 链表： 适用于顺序访问数据
- 可预测的性能： 当最坏情况很重要时
来源
本教程介绍了 PHP 中的归并排序算法，并提供了不同数据类型和排序顺序的示例，以及性能比较。
作者
列出 所有 PHP 教程。