PHP 桶排序算法
最后修改于 2025 年 4 月 16 日
基本定义
一个算法是解决问题的分步过程。它接受输入，并按照一组定义的规则产生输出。
排序将数据按特定顺序排列（升序或降序）。有效的排序对于优化其他算法至关重要。
常见的排序算法包括
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
- 桶排序
- 基数排序
桶排序概述
桶排序将元素分配到桶中，对每个桶进行排序，然后将它们连接起来。当输入均匀分布时，效果很好。
时间复杂度：最佳情况为 O(n + k)，最坏情况为 O(n²)。空间复杂度：O(n + k)，其中 k 是桶的数量。
数字桶排序（升序）
此示例使用桶排序按升序对数字进行排序。
numeric_ascending.php
<?php
function bucketSort(array $numbers): array {
$min = min($numbers);
$max = max($numbers);
$bucketCount = count($numbers);
$range = ($max - $min) / $bucketCount;
$buckets = array_fill(0, $bucketCount, []);
foreach ($numbers as $num) {
$index = floor(($num - $min) / $range);
$index = min($index, $bucketCount - 1);
$buckets[$index][] = $num;
}
$sorted = [];
foreach ($buckets as $bucket) {
sort($bucket);
$sorted = array_merge($sorted, $bucket);
}
return $sorted;
}
$numbers = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51];
$sorted = bucketSort($numbers);
print_r($sorted);
输出显示按升序排序的数字。该算法首先根据数值范围将数字分配到桶中。
数字桶排序（降序）
这修改了前面的示例，以按降序排序。
numeric_descending.php
<?php
function bucketSortDesc(array $numbers): array {
$min = min($numbers);
$max = max($numbers);
$bucketCount = count($numbers);
$range = ($max - $min) / $bucketCount;
$buckets = array_fill(0, $bucketCount, []);
foreach ($numbers as $num) {
$index = floor(($num - $min) / $range);
$index = min($index, $bucketCount - 1);
$buckets[$index][] = $num;
}
$sorted = [];
foreach ($buckets as $bucket) {
rsort($bucket);
$sorted = array_merge($sorted, $bucket);
}
return $sorted;
}
$numbers = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51];
$sorted = bucketSortDesc($numbers);
print_r($sorted);
关键的变化是使用rsort()而不是sort()在合并之前按降序对各个桶进行排序。
字符串桶排序（升序）
桶排序也可以按字母顺序对字符串进行排序。此示例演示了如何操作。
string_ascending.php
<?php
function bucketSortStrings(array $strings): array {
$minOrd = ord('a');
$maxOrd = ord('z');
$bucketCount = 26; // One for each letter
$buckets = array_fill(0, $bucketCount, []);
foreach ($strings as $str) {
$firstChar = strtolower(substr($str, 0, 1));
$index = ord($firstChar) - $minOrd;
$buckets[$index][] = $str;
}
$sorted = [];
foreach ($buckets as &$bucket) {
sort($bucket);
$sorted = array_merge($sorted, $bucket);
}
return $sorted;
}
$names = ["Alice", "Bob", "Charlie", "David", "Eve", "Frank"];
$sorted = bucketSortStrings($names);
print_r($sorted);
字符串根据其首字母分配到桶中。然后，在合并之前，每个桶按字母顺序排序。
字符串桶排序（降序）
此版本按逆字母顺序对字符串进行排序。
string_descending.php
<?php
function bucketSortStringsDesc(array $strings): array {
$minOrd = ord('a');
$maxOrd = ord('z');
$bucketCount = 26;
$buckets = array_fill(0, $bucketCount, []);
foreach ($strings as $str) {
$firstChar = strtolower(substr($str, 0, 1));
$index = ord($firstChar) - $minOrd;
$buckets[$index][] = $str;
}
$sorted = [];
foreach ($buckets as &$bucket) {
rsort($bucket);
$sorted = array_merge($sorted, $bucket);
}
return array_reverse($sorted);
}
$names = ["Alice", "Bob", "Charlie", "David", "Eve", "Frank"];
$sorted = bucketSortStringsDesc($names);
print_r($sorted);
我们使用rsort()用于桶，使用array_reverse()用于最终结果，以获得降序字母顺序。
桶排序 vs 快速排序基准测试
让我们比较一下桶排序和快速排序在大型数据集上的性能。
benchmark.php
<?php
function quickSort(array $array): array {
if (count($array) < 2) {
return $array;
}
$pivot = $array[0];
$less = $greater = [];
for ($i = 1; $i < count($array); $i++) {
if ($array[$i] <= $pivot) {
$less[] = $array[$i];
} else {
$greater[] = $array[$i];
}
}
return array_merge(quickSort($less), [$pivot], quickSort($greater));
}
// Generate large random dataset
$largeData = [];
for ($i = 0; $i < 10000; $i++) {
$largeData[] = mt_rand(0, 10000) / 100;
}
// Benchmark bucket sort
$start = microtime(true);
bucketSort($largeData);
$bucketTime = microtime(true) - $start;
// Benchmark quick sort
$start = microtime(true);
quickSort($largeData);
$quickTime = microtime(true) - $start;
echo "Bucket Sort Time: " . number_format($bucketTime, 6) . " seconds\n";
echo "Quick Sort Time: " . number_format($quickTime, 6) . " seconds\n";
结果会有所不同，但通常快速排序在一般情况下优于桶排序。当数据均匀分布时，桶排序表现出色。
何时使用桶排序
- 均匀分布：当输入均匀分布时
- 已知范围：当数据范围提前已知时
- 浮点数：特别适用于浮点数
- 外部排序：适用于外部排序场景
来源
本教程涵盖了 PHP 实现的桶排序，并提供了数值和文本数据升序和降序的示例。
作者
列出 所有 PHP 教程。