冒泡排序

<?php
//冒泡排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
for($i = 0; $i < $num; $i++) {
    for($j = 0; $j < $num - $i - 1; $j++){         $total++;         if($arr[$j] > $arr[$j+1]) {
            $temp       = $arr[$j];
            $arr[$j]    = $arr[$j+1];
            $arr[$j+1]  = $temp;
        }
    }
}
echo $total;//66次循环
print_r($arr);

优化：
如果内层循环没有进行交互则表示已经排序完成

$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$total = 0;
$num = count($arr);
$break = false;
for($i = 0; $i < $num; $i++) {
    $break = true;
    for($j = 0; $j < $num - $i - 1; $j++){         $total++;         if($arr[$j] > $arr[$j+1]) {
            $temp       = $arr[$j];
            $arr[$j]    = $arr[$j+1];
            $arr[$j+1]  = $temp;
            $break = false;
        }
    }
    if($break) {
        break;
    }
}
echo $total;//45次循环
print_r($arr);
//优化第二步    
//缩减内层循环排序区间，如果0到i的位置是有序，那么上次循环区间是i到n
//交换的位置在i到n之间的pos位置
//其中可以知道i到pos的位置是有序的，那么下次循环就可以从post到n
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
$break = false;
$lastSwapPos  = $lastSwap = 0;
for($i = 0; $i < $num - 1; $i++) {     $lastSwap = $lastSwapPos;     for($j = $num - 1; $j > $lastSwap; $j--){
        $total++;
        if($arr[$j - 1] > $arr[$j]) {
            $temp       = $arr[$j];
            $arr[$j]    = $arr[$j - 1];
            $arr[$j - 1]  = $temp;
            $lastSwapPos = $j;
        }
    }
    if($lastSwap == $lastSwapPos) {
        break;
    }
}
echo $total;//39次循环
print_r($arr);
//双向冒泡(鸡尾酒排序)
/*
原理
数组中的数字本是无规律的排放，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位。
然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序
*/
//冒泡排序
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$num = count($arr);
$total = 0;
$left = 0;
$right = $num - 1;
while ($left < $right) {
    $l = $left + 1;
    $r = $right - 1;
    for($i = $left; $i < $right; $i++) {
        $total++;
        if($arr[$i] > $arr[$i+1]) {
            $temp1 = $arr[$i];
            $arr[$i] = $arr[$i+1];
            $arr[$i+1] = $temp1;
            $r = $i;
        }
    }
    $right = $r;
    for($j = $right;$j > $left; $j--) {
        $total++;
        if($arr[$j] < $arr[$j - 1]) {
            $temp2 = $arr[$j-1];
            $arr[$j - 1] = $arr[$j];
            $arr[$j] = $temp2;
            $l = $j;
        }
    }
    $left = $l;
    
}
echo $total;//30次循环
print_r($arr);