冒泡排序也是一種簡(jiǎn)單直觀的排序算法。其思想是：它重復(fù)地走訪(fǎng)過(guò)要排序的數(shù)列柱告，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)际度。走訪(fǎng)數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換葵袭，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端乖菱。
下面我們通過(guò)一個(gè)簡(jiǎn)單的圖例來(lái)了解一下這個(gè)冒泡的過(guò)程
起始位置為0坡锡，依次比較相鄰的兩個(gè)元素。如果前面的元素大于后面的元素窒所，則進(jìn)行交換鹉勒。
我們可以看出，待排序序列有多少個(gè)元素吵取，就需要幾趟冒泡禽额。但是在實(shí)際過(guò)程中，我們可以根據(jù)實(shí)際情況減少其冒泡的趟數(shù)皮官。
就拿上例來(lái)說(shuō)脯倒，我們看在第四趟冒泡完成以后就已經(jīng)有序了。第五趟和第六趟冒泡過(guò)程并沒(méi)有產(chǎn)生元素的交換捺氢。所以說(shuō)我們可以判斷藻丢，在一趟冒泡中如果沒(méi)有產(chǎn)生元素的交換，我們就終止冒泡的整個(gè)過(guò)程摄乒。這樣最后得到的序列同樣是有序的悠反。
反應(yīng)在程序中就是在每一趟冒泡的開(kāi)始設(shè)置一個(gè)標(biāo)志位，默認(rèn)為false馍佑。當(dāng)有交換產(chǎn)生的時(shí)候?qū)⒃摌?biāo)志位設(shè)為true斋否。在該趟冒泡過(guò)程結(jié)束以后，我們根據(jù)此標(biāo)志位來(lái)判斷是否有交換的產(chǎn)生拭荤。如果沒(méi)有交換產(chǎn)生的話(huà)如叼，我們就直接結(jié)束整個(gè)冒泡過(guò)程。否則繼續(xù)下一趟冒泡穷劈。
根據(jù)上圖笼恰，我們來(lái)看一下實(shí)現(xiàn)冒泡排序的文字的步驟
1）比較相鄰的元素踊沸。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)社证。
2）對(duì)每一對(duì)相鄰元素作同樣的工作逼龟，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后追葡，最后的元素會(huì)是最大的數(shù)腺律。
3）針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)宜肉。
4）持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟匀钧，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
最后我們要將文字步驟轉(zhuǎn)換成代碼實(shí)現(xiàn)
/**
* 交換函數(shù)
*/
function swap(&$arr,$a,$b){
$t = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $t;
}
function BubbleSort(&$arr){
$end = count($arr)-1;
while($end>0){
for($i=0;$i<$end;$i++){
if($arr[$i]>$arr[$i+1]){
swap($arr,$i,$i+1);
}
}
$end--;
}
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
BubbleSort($arr);
print_r($arr);
上述代碼是將所有的冒泡過(guò)程都走了一遍谬返，下面我們只需要將BubbleSort函數(shù)進(jìn)行簡(jiǎn)單的修改就可以實(shí)現(xiàn)上述我們說(shuō)的標(biāo)志位來(lái)判斷是否有交換的產(chǎn)生之斯。
function BubbleSort(&$arr){
$end = count($arr)-1;
while($end>0){
$flag = false; //每次冒泡前 初始化標(biāo)志位為false
for($i=0;$i<$end;$i++){
if($arr[$i]>$arr[$i+1]){
swap($arr,$i,$i+1);
$flag = true; //有交換產(chǎn)生 將標(biāo)志位置為true
}
}
if(!$flag) break; //如果沒(méi)有交換產(chǎn)生 則直接跳出循環(huán)
$end--;
}
}
其實(shí)帶標(biāo)志位的和不帶標(biāo)志位的程序在數(shù)據(jù)量很小的時(shí)候并沒(méi)有明顯的差別，所用時(shí)間應(yīng)該沒(méi)有什么差別遣铝。但是在數(shù)據(jù)量很大的時(shí)候其差別就會(huì)變得很明顯佑刷。但是話(huà)又說(shuō)回來(lái)，冒泡排序并不是最好的排序算法酿炸，其效率較其他的排序算法低瘫絮，時(shí)間復(fù)雜度為O(n2)。所以說(shuō)在實(shí)際情況中如果數(shù)據(jù)量很大的話(huà)也不一定我們會(huì)選擇冒泡排序來(lái)實(shí)現(xiàn)排序填硕。
但是我個(gè)人覺(jué)得冒泡排序和選擇排序可以說(shuō)是其他排序的基礎(chǔ)麦萤，所以我們有必要去了解冒泡排序。
希望本文對(duì)大家有所幫助扁眯。
