基本思想：
冒泡排序是一種交換排序闸拿，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換书幕，直到?jīng)]有反序的記錄為止新荤。
最簡單的排序?qū)崿F(xiàn)：
//這里使用了類型提示（type hint） array，不熟悉或者不習(xí)慣的同學(xué)大可去掉台汇，不影響運(yùn)算結(jié)果
function MySort(array &$arr){
? ? ? $length = count($arr);
? ? ? for($i = 0;$i < $length - 1;$i ++){
? ? ? ? ? ? for($j = $i + 1;$j < $length;$j ++){
? ? ? ? ? ? ? ? ? //將小的關(guān)鍵字放前面
? ? ? ? ? ? ? ? ? if($arr[$i] > $arr[$j]){
? ? ? ? ? ? ? ? ? ? ? ? $temp = $arr[$i];
? ? ? ? ? ? ? ? ? ? ? ? $arr[$i] = $arr[$j];
? ? ? ? ? ? ? ? ? ? ? ? ? $arr[$j] = $temp;
? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ?}
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
上面的這段代碼嚴(yán)格意義上說苛骨，不算是標(biāo)準(zhǔn)的冒泡排序，因?yàn)樗粷M足“兩兩比較相鄰記錄”的冒泡排序思想苟呐，它僅僅是一個(gè)簡單的交換排序痒芝。思路不過是：從第一個(gè)關(guān)鍵字開始，將每一位關(guān)鍵字與它后面的所有關(guān)鍵字相比較掠抬，交換得到其中的最小值吼野。但這個(gè)算法是非常低效的。
冒泡排序算法：
? ? ? ? 它重復(fù)地走訪過要排序的數(shù)列两波，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來闷哆。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換腰奋，也就是說該數(shù)列已經(jīng)排序完成。
這個(gè)算法的名字由來是因?yàn)閿?shù)組中越大的元素會(huì)由于一次次排序后逐漸“沉”到數(shù)組的后面抱怔，而越小的元素會(huì)逐漸“浮”到數(shù)組的前面劣坊，故名。
冒泡排序算法的運(yùn)作如下：（從后往前）
? ? ? ? ? ? 比較相鄰的元素屈留。如果第一個(gè)比第二個(gè)大局冰，就交換他們兩個(gè)测蘑。
? ? ? ? ? ? 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)康二。在這一點(diǎn)碳胳，最后的元素應(yīng)該會(huì)是最大的數(shù)。
? ? ? ? ? ? 針對(duì)所有的元素重復(fù)以上的步驟沫勿，除了最后一個(gè)挨约。
? ? ? ? ? ? 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)产雹。
看文字描述不一定看得懂诫惭，看代碼吧：
//交換方法
function ? swap(array &$arr,$a,$b){
? ? ? ? ?$temp=$arr[$a];
? ? ? ? ? $arr[$a] =$arr[$b];
? ? ? ? ?$arr[$b] =$temp;
}
//冒泡排序
function ?BubbleSort(array &$arr){
? ? ? ? ? $length= count($arr);
? ? ? ? ? for($i=0;$i<$length-1;$i++){
? ? ? ? ? ?//從后往前逐層上浮小的元素
? ? ? ? ? ? ? ? ?for($j=$length-2;$j>=$i;$j--){
? ? ? ? ? ? ? ? ?//兩兩比較相鄰記錄
? ? ? ? ? ? ? ? ? ? ? ? ? if($arr[$j] >$arr[$j+1]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? swap($arr,$j,$j+1);
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? }
}
冒泡排序算法改進(jìn)：
《大話數(shù)據(jù)結(jié)構(gòu)》果然是本好書，還給我們介紹了冒泡排序算法的改進(jìn)蔓挖，這里我就直接搬它的陳述：
上面的冒泡排序算法是否還可以優(yōu)化呢夕土？答案是肯定的。試想一下瘟判，如果我們待排序的序列是{2,1,3,4,5,6,7,8,9}怨绣，也就是說，除了第一和第二個(gè)關(guān)鍵字需要交換外荒适，別的都已經(jīng)是正常的順序了梨熙。當(dāng) i = 0 時(shí)，交換了 2 和 1 刀诬，此時(shí)的序列已經(jīng)是有序的了咽扇，但是算法仍然不依不撓地將 i = 2 到 9 以及每個(gè)循環(huán)中的 j 循環(huán)都執(zhí)行了一遍，盡管并沒有交換數(shù)據(jù)陕壹，但是之后的大量比較還是大大地多余了质欲。
當(dāng) i = 2 時(shí)，我們已經(jīng)對(duì) 9 與 8糠馆，8 與 7嘶伟，·······，3 與 2 做了比較又碌，沒有任何數(shù)據(jù)交換九昧，這就說明此序列已經(jīng)有序，不需要再繼續(xù)后面的循判斷工作了（后面的工作也是不會(huì)發(fā)生任何數(shù)據(jù)交換毕匀，再做也是沒有意義了）铸鹰。為了實(shí)現(xiàn)這個(gè)想法，我們需要改進(jìn)一下代碼皂岔，增加一個(gè)標(biāo)記變量 flag 來實(shí)現(xiàn)這一算法的改進(jìn)：
//交換方法
function ? ? swap(array &$arr,$a,$b){
$temp=$arr[$a];
$arr[$a] =$arr[$b];
$arr[$b] =$temp;
}
/冒泡排序的優(yōu)化(如果某一次循環(huán)的時(shí)候沒有發(fā)生元素的交換蹋笼，則整個(gè)數(shù)組已經(jīng)是有序的了)
function ? ?BubbleSort1(array &$arr){
? ? ? ? ? ? ? ? ? ?$length= count($arr);
? ? ? ? ? ? ? ? ? ? $flag=TRUE;
? ? ? ? ? ? ? ? ? ? for($i=0;($i<$length-1) &&$flag;$i++){
? ? ? ? ? ? ? ? ? ? ? ? ? ? $flag=FALSE;
? ? ? ? ? ? ? ? ? ? ? ? ? ? for($j=$length-2;$j>=$i;$j--){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if($arr[$j] >$arr[$j+1]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?swap($arr,$j,$j+1);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?$flag=TRUE;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ?}
}
代碼改動(dòng)的關(guān)鍵就是在 i 變量的for循環(huán)中，增加了對(duì)flag是否為 true 的判斷，經(jīng)過這樣的改進(jìn)剖毯，冒泡排序在性能上就有了一些提升圾笨，可以避免因已經(jīng)有序的情況下的無意義循環(huán)判斷。
冒泡算法總的時(shí)間復(fù)雜度是 O(n^2)逊谋。
冒泡排序是穩(wěn)定排序擂达。
