冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序是一种稳定的排序算法。
由于冒泡排序的时间复杂度较高(O(n^2)),通常只适用于小规模数据的排序。例如:
以下是PHP实现冒泡排序的示例代码:
<?php
function bubbleSort($arr) {
$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;
}
// 测试
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: \n";
print_r($arr);
echo "\n排序后的数组: \n";
print_r(bubbleSort($arr));
?>
原因:冒泡排序的时间复杂度为O(n^2),因为它需要进行多轮比较和交换操作,每轮都会将当前未排序部分的最大(或最小)元素移动到正确的位置。
解决方法:
<?php
function bubbleSortOptimized($arr) {
$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]) {
// 交换元素
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$swapped = true;
}
}
// 如果没有发生交换,提前结束
if (!$swapped) {
break;
}
}
return $arr;
}
// 测试
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: \n";
print_r($arr);
echo "\n排序后的数组: \n";
print_r(bubbleSortOptimized($arr));
?>
通过上述优化,可以在一定程度上提高冒泡排序的效率。
领取专属 10元无门槛券
手把手带您无忧上云