PHP 冒泡排序算法
最后修改于 2025 年 4 月 16 日
基本定义
算法 是一种逐步解决问题或执行计算的程序。在编程中，算法被实现为函数或方法。
排序是将数据按特定顺序排列，通常是升序或降序。 有效的排序对于优化需要排序输入的其他算法至关重要。
常见的排序算法包括
- 气泡排序
- 快速排序
- 归并排序
- 插入排序
- 选择排序
- 堆排序
气泡排序算法
冒泡排序是一种简单的基于比较的算法。 它重复遍历列表，比较相邻的元素，如果它们的顺序错误则交换它们。
该算法得名于较小的元素“冒泡”到列表的顶部。 它的时间复杂度为 O(n²)，这使得它对于大型数据集效率低下。
基本冒泡排序实现
这是 PHP 中用于数值数据的冒泡排序的基本实现
bubble_sort.php
<?php
function bubbleSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
// Swap elements
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
$numbers = [64, 34, 25, 12, 22, 11, 90];
$sorted = bubbleSort($numbers);
print_r($sorted);
// Output: Array ( [0] => 11 [1] => 12 [2] => 22 [3] => 25 [4] => 34 [5] => 64 [6] => 90 )
优化后的冒泡排序
我们可以通过添加一个标志来优化冒泡排序，以检查一次遍历中是否进行了任何交换。 如果没有交换发生，则该数组已排序。
optimized_bubble.php
<?php
function optimizedBubbleSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
$swapped = false;
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
// Swap elements
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$swapped = true;
}
}
// If no swaps, array is sorted
if (!$swapped) break;
}
return $arr;
}
$numbers = [5, 1, 4, 2, 8];
$sorted = optimizedBubbleSort($numbers);
print_r($sorted);
// Output: Array ( [0] => 1 [1] => 2 [2] => 4 [3] => 5 [4] => 8 )
降序排序
要以降序排序，我们只需反转比较条件。
descending_bubble.php
<?php
function bubbleSortDesc(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] < $arr[$j + 1]) { // Changed comparison operator
// Swap elements
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
$numbers = [64, 34, 25, 12, 22, 11, 90];
$sorted = bubbleSortDesc($numbers);
print_r($sorted);
// Output: Array ( [0] => 90 [1] => 64 [2] => 34 [3] => 25 [4] => 22 [5] => 12 [6] => 11 )
对文本数据进行排序
冒泡排序还可以通过使用 strcmp 函数比较字符串来按字母顺序对字符串进行排序。
text_bubble.php
<?php
function bubbleSortText(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if (strcmp($arr[$j], $arr[$j + 1]) > 0) {
// Swap elements
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
$names = ["John", "Alice", "Bob", "Eve", "David"];
$sorted = bubbleSortText($names);
print_r($sorted);
// Output: Array ( [0] => Alice [1] => Bob [2] => David [3] => Eve [4] => John )
冒泡排序与快速排序基准测试
让我们将冒泡排序与更有效的快速排序算法进行比较。 我们将测量对大型数组进行排序的执行时间。
sort_benchmark.php
<?php
function bubbleSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n - 1; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
function quickSort(array $arr): array {
if (count($arr) <= 1) return $arr;
$pivot = $arr[0];
$left = $right = [];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
return array_merge(quickSort($left), [$pivot], quickSort($right));
}
// Generate large array
$largeArray = range(1, 2000);
shuffle($largeArray);
// Benchmark Bubble Sort
$start = microtime(true);
bubbleSort($largeArray);
$bubbleTime = microtime(true) - $start;
// Benchmark Quick Sort
$start = microtime(true);
quickSort($largeArray);
$quickTime = microtime(true) - $start;
printf("Bubble Sort time: %.4f seconds\n", $bubbleTime);
printf("Quick Sort time: %.4f seconds\n", $quickTime);
// Typical output:
// Bubble Sort time: 1.2345 seconds
// Quick Sort time: 0.0123 seconds
基准测试清楚地表明了快速排序对于大型数据集的卓越性能。 冒泡排序的 O(n²) 复杂度使其不适用于大型数组，而快速排序的 O(n log n) 表现更好。
何时使用冒泡排序
尽管效率不高，但冒泡排序有一些用例
- 用于理解排序算法的教育目的
- 当简单性比性能更重要时
- 对于几乎已排序的数据（使用优化版本）
- 处理非常小的数据集时
来源
本教程涵盖了 PHP 中的冒泡排序算法，并提供了数值和文本数据的示例，包括性能比较。
作者
列出 所有 PHP 教程。