PHP 堆排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法是一种逐步解决问题或执行计算的程序。排序算法将元素按特定顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。 它们各有不同的时间复杂度。
堆排序概述
堆排序是一种基于比较的排序算法，它使用二叉堆数据结构。 它的时间复杂度为 O(n log n)，适用于所有情况。
该算法首先从输入数据构建一个最大堆。 然后它重复提取最大元素并重建堆。
堆排序实现
这是一个 PHP 中用于数值数据的基本堆排序实现
heap_sort.php
<?php
function heapSort(array &$arr): void {
$n = count($arr);
// Build max heap
for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
heapify($arr, $n, $i);
}
// Extract elements one by one
for ($i = $n - 1; $i > 0; $i--) {
// Move current root to end
[$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
// Heapify reduced heap
heapify($arr, $i, 0);
}
}
function heapify(array &$arr, int $n, int $i): void {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $n && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
if ($largest != $i) {
[$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
heapify($arr, $n, $largest);
}
}
$numbers = [12, 11, 13, 5, 6, 7];
heapSort($numbers);
print_r($numbers);
此实现首先从输入数组构建一个最大堆。 然后它重复提取最大元素并维护堆属性。
对文本数据进行排序
堆排序也可以按字母顺序对字符串进行排序。 这是一个例子
heap_sort_strings.php
<?php
function heapSortStrings(array &$arr): void {
$n = count($arr);
for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
heapifyStrings($arr, $n, $i);
}
for ($i = $n - 1; $i > 0; $i--) {
[$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
heapifyStrings($arr, $i, 0);
}
}
function heapifyStrings(array &$arr, int $n, int $i): void {
$largest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && strcmp($arr[$left], $arr[$largest]) > 0) {
$largest = $left;
}
if ($right < $n && strcmp($arr[$right], $arr[$largest]) > 0) {
$largest = $right;
}
if ($largest != $i) {
[$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
heapifyStrings($arr, $n, $largest);
}
}
$words = ["banana", "apple", "cherry", "date"];
heapSortStrings($words);
print_r($words);
此版本使用 strcmp 进行字符串比较。 该算法的工作方式相同，但比较的是字符串而不是数字。
降序排序
要按降序排序，我们修改堆化函数以创建最小堆而不是最大堆
heap_sort_descending.php
<?php
function heapSortDescending(array &$arr): void {
$n = count($arr);
for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
heapifyDescending($arr, $n, $i);
}
for ($i = $n - 1; $i > 0; $i--) {
[$arr[0], $arr[$i]] = [$arr[$i], $arr[0]];
heapifyDescending($arr, $i, 0);
}
}
function heapifyDescending(array &$arr, int $n, int $i): void {
$smallest = $i;
$left = 2 * $i + 1;
$right = 2 * $i + 2;
if ($left < $n && $arr[$left] < $arr[$smallest]) {
$smallest = $left;
}
if ($right < $n && $arr[$right] < $arr[$smallest]) {
$smallest = $right;
}
if ($smallest != $i) {
[$arr[$i], $arr[$smallest]] = [$arr[$smallest], $arr[$i]];
heapifyDescending($arr, $n, $smallest);
}
}
$numbers = [12, 11, 13, 5, 6, 7];
heapSortDescending($numbers);
print_r($numbers);
此实现找到最小的元素而不是最大的元素，从而得到降序。 同样的方法也适用于字符串，通过修改比较。
堆排序与快速排序
堆排序和快速排序都是高效的排序算法，平均时间复杂度为 O(n log n)。 但是，它们具有不同的特性。
快速排序通常在实践中更快，因为它具有更好的缓存性能和更小的常数因子。 然而，堆排序在最坏情况下保证了 O(n log n) 的性能。
基准测试比较
让我们通过基准测试比较堆排序和快速排序的性能
sort_benchmark.php
<?php
function quickSort(array &$arr, int $low, int $high): void {
if ($low < $high) {
$pi = partition($arr, $low, $high);
quickSort($arr, $low, $pi - 1);
quickSort($arr, $pi + 1, $high);
}
}
function partition(array &$arr, int $low, int $high): int {
$pivot = $arr[$high];
$i = $low - 1;
for ($j = $low; $j <= $high - 1; $j++) {
if ($arr[$j] < $pivot) {
$i++;
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
[$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
return $i + 1;
}
// Generate large random array
$largeArray = [];
for ($i = 0; $i < 10000; $i++) {
$largeArray[] = rand(1, 100000);
}
// Benchmark heap sort
$heapArray = $largeArray;
$heapStart = microtime(true);
heapSort($heapArray);
$heapTime = microtime(true) - $heapStart;
// Benchmark quick sort
$quickArray = $largeArray;
$quickStart = microtime(true);
quickSort($quickArray, 0, count($quickArray) - 1);
$quickTime = microtime(true) - $quickStart;
echo "Heap sort time: " . number_format($heapTime, 6) . " seconds\n";
echo "Quick sort time: " . number_format($quickTime, 6) . " seconds\n";
此基准测试创建一个大的随机数组，并测量两种算法的排序时间。 快速排序通常在随机数据上表现更好。
何时使用堆排序
- 最坏情况保证： 当您需要保证 O(n log n) 的性能时。
- 内存限制： 堆排序是原地排序 (O(1) 空间)。
- 外部排序： 用于排序不适合内存的数据。
- 优先级队列： 堆结构在排序之外也很有用。
来源
本教程涵盖了 PHP 堆排序算法，并提供了数值和文本数据的示例，包括升序和降序排序。
作者
列出 所有 PHP 教程。