PHP写排序算法（一）冒泡排序

冒泡排序

依次比较相邻的两个元素，每次比较完毕最大的一个字跑到本轮的末尾。

例如：

$arr=[26,76,43,41,86,1,45,49,71,4];

第一轮比较相邻两个元素，如果左边元素大于右边元素，则交换。

26和76比较的结果就是，26在前，76在后；
然后76和43比较的结果，43在前，76在后；
然后76和41比较的结果，41在前，76在后；
然后76和86比较的结果，76在前，86在后；
然后86和1比较的结果，1在前，86在后；
然后86和45比较的结果，45在前，86在后；
然后86和49比较的结果，49在前，86在后；
然后86和71比较的结果，71在前，86在后；
然后86和4比较的结果，4在前，86在后；

以此类推，第一轮比较之后的结果是：26，43，41，76，1，45，49，71，4，86。经过第一轮比较，最大的元素跑到了最后一个，所以第二轮比较，最后一个元素不需要进行比较了。  第三轮还是从索引0和1开始比较，最后两个不比较了。第四轮、第五轮以此类推。

$arr=[26,76,43,41,86,1,45,49,71,4];  

// 冒泡排序
function maopao(array $arr) :array{  
$len=count($arr);  
for ($i=0; $i <$len ; $i++) {  
    # code...  
    for ($j=0; $j <$len-$i-1; $j++) {  
        # code...  
        if($arr[$j]>$arr[$j+1]) {  
            # code...  
            $t=$arr[$j];  
            $arr[$j]=$arr[$j+1];  
            $arr[$j+1]=$t;  
        }  
    }  
    var_dump($arr);  
}  
return $arr;  
}  
var_dump(maopao($arr));  

每次比较结果：

时间复杂度：

从代码中可以看出一共遍历了n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 - 0.5 * n，那么时间复杂度是O(N^2)。

稳定性：

因为arr[j]==arr[j+1]的时候，我们可以不移动arr[j]和arr[j++]，所以冒泡排序是稳定的。