算法系列：冒泡排序法

一、基本思路

通過兩兩比較，然后交換雙方位置的一種排序方法。

二、示例代碼

$arr = array(1,4,2,6,3,8);
for($i=0;$i<count($arr)-1;$i++){    
    for($j=$i+1;$j<count($arr);$j++){       

        if($arr[$i]>$arr[$j]){  //如果前面的數比后面的大，則進行交換     
            $temp = $arr[$j];           
            $arr[$j] = $arr[$i];
            $arr[$i] = $temp;           
        }
    }
}
//$arr = array(1,2,3,4,6,8)

三、分析說明

1、需要兩層循環
2、第一層循環從第一個數開始，截止到倒數第二個數
3、第二層循環從第一個數的后面開始，截止到最后一個數。
4、當前面的數比后面的大時，進行位置互換，互換需要一個臨時變量。

四、復雜度分析

1、第一層循環需要執行n-1次，第二層循環也要執行n-1次
2、總執行次數為(n-1)*(n-1) = n^2 - 2n + 1
3、時間復雜度為n^2

數量n 執行次數

2 1

3 4

4 9

5 16

... ...

101 10000

五、備注

冒泡法思路簡單，實現簡單，對于數據規模比較小的情況下適合使用。

六、雙向冒泡（雞尾酒冒泡）

這是一種左到右，右到左，反復掃描排序模式，整體排序效率略高于單向冒泡，但是實現起來復雜的多。

當待排序數組比較規則時（大部分已排序）效率比單向冒泡高。

//交換函數
function swap(&$arr,$i,$j){

    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;

    return $arr;
}
//向右排序（大的往右放）
function leftSort(&$arr,$left,$right){

    for($i=$left;$i<$right;$i++){

        if($arr[$i]>$arr[$i+1]){

            swap($arr,$i,$i+1);
        }
    }   
}
//向左排序（小的往左放）
function rightSort(&$arr,$right,$left){

    for($i=$right;$i>$left;$i--){

        if($arr[$i-1]>$arr[$i]){

            swap($arr,$i-1,$i);
        }
    }
}

function CocktailSort(&$arr,$n){

    $left = 0;
    $right = $n-1;

    while($left < $right){

        leftSort($arr,$left,$right);
        $right -=1;
        rightSort($arr,$right,$left);
        $left +=1;  
    }
}

$arr = array(1,4,2,6,3,8);
$n = count($arr);
CocktailSort($arr,$n);

//arr = array(1,2,3,4,6,8);