冒泡排序是最简单的排序算法。冒泡排序基于这样的思想:如果发现顺序错误，则对每个相邻元素进行比较和交换。
示例:
要理解冒泡排序，让我们考虑一个未排序的数组 [1, 23, 10, -2] 并讨论按升序对数组进行排序所采取的每个步骤。在每次传递中，都会检查两个相邻元素，如果发现顺序错误则进行交换。
第一遍: 通过 (1) 和 (23) 进行比较并发现正确的顺序（在本例中为升序）。之后比较 (23) 和 (10)，因为 (23>10)，因此这些数字被交换。然后比较并交换 (23) 和 (-2)。
第二遍: 比较(1)和(10)并发现顺序正确。然后比较 (10) 和 (-2)，因为 (10>-2)，因此这些数字被交换。之后，比较(10)和(23)并按正确的顺序找到。
第三遍 : (1) 和 (-2) 进行比较，因为 (1>-2)，因此这些数字被交换。之后检查 (1,10) 和 (10,23) 并按正确顺序找到。
冒泡排序的实现
<?php
// 冒泡排序函数
function bubblesort(&$Array, $n) {
$temp;
for($i=0; $i<$n; $i++) {
for($j=0; $j<$n-$i-1; $j++) {
if($Array[$j]>$Array[$j+1]) {
$temp = $Array[$j];
$Array[$j] = $Array[$j+1];
$Array[$j+1] = $temp;
}
}
}
}
//打印数组的函数
function PrintArray($Array, $n) {
for ($i = 0; $i < $n; $i++)
echo $Array[$i]." ";
echo "\n";
}
//测试代码
$MyArray = array(1, 10, 23, 50, 4, 9, -4);
$n = sizeof($MyArray);
echo "原始数组\n";
PrintArray($MyArray, $n);
bubblesort($MyArray, $n);
echo "\n排序数组\n";
PrintArray($MyArray, $n);
?> 上面的代码将给出以下输出:
原始数组
1 10 23 50 4 9 -4
排序数组
-4 1 4 9 10 23 50 时间复杂度:
在所有情况下，即使整个数组已排序，冒泡排序的时间复杂度也是θ(N²)，因为整个数组的每个元素都需要迭代，它包含两个嵌套循环。