首先說說冒泡排序的思想,那很多同學會問什麼是冒泡排序法呢?
下面我來解釋下:
所謂的冒泡排序法,就是依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。
咱們來看個例子:
有一個數組array(23,34,12,56,43,98,89),下面我們來使用冒泡排序法來對其元素進行排序.
<?php
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i<count($arr);$i++){
for($j=0;$j<count($arr)-1;$j++){
if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>
在上面的例子中,裡面的for循環,是將本數組中的所有元素依次兩兩相比,也就是將數組中的第一個元素和第二個元素相比,第二個元素與第三個元素相比,
依此類推,直到數組的倒數第二個元素與最後一個元素相比,如果前面的元素大於後面的元素就讓前面的元素與後面的元素位置交換,
那我們想,怎麼讓數組中的兩個元素位置交換呢,
我們可以使用一個中間的容器變量來解決這個問題,
也就是將需要交換的第一個變量的值放入容器變量,然後將需要交換的第二個變量的值賦給第一個變量,再將容器變量中的值賦給第二個變量即可.
為了讓大家更深刻的理解,請看下面的模擬圖:
第一步:聲明一個中間容器變量$tmp:
第二步:將$arr[$j]的值賦給$tmp
第三步:將$arr[$j+1]賦值給$arr[$j]
第四步:將中間變量的值賦給$arr[$j+1],完成交換
依次類推,一直到數組的倒數第二個元素與最後一個元素比較完成.總共比較count($arr)-1次
至此,我們數組的第一趟排序也就完成,此時數組中最大的數已經放到了數組的最後.也就是說,內層的for循環已經執行完成. www.2cto.com
接下來我們需要進行第二趟,第三趟....排序,每排一趟,出一個最大的數放在數組後面,只要排完,總共排count($arr)趟.
說到這裡,大家是不是明白外層for循環的意思了呢!
好,我們思考一個問題,如果數組內的元素兩兩比較完,每比較一趟排出一個最大數,
那我們是不是在下趟比較的時候,不執行和上趟排出來的最大數的比較呢,
也就是說,第一趟排序完,98已經被放到了數組的最後,下趟排序就無需再把98拿來比較了,這樣會提高效率,節省資源,
因此我們可以這樣寫:
<?php
$arr = Array(23,34,12,56,43,98,89);
for($i=0;$i<count($arr);$i++){
for($j=0;$j<count($arr)-$i;$j++){
if($j==count($arr)-1){
continue;
}
if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>
上述代碼中,內層循環執行次數變成了count($arr)-$i,
也就是說每趟把數組內的所有元素兩兩比較完之後,下趟再進行此排序時,排序的次數會減一,
也就是排除上一趟比較得出的最大的數的比較,這樣一來,效率會提升不少,
我們可以使用php的內建函數microtime()在執行排序前執行一次,在排序後執行一次,將兩次的時間相減,即得出運算時間,
通過比較可以得出冒泡排序的第二種排序方法的效率要高於第一種排序方法,但不是很明顯,大家下來可以驗證下,這裡就不多講了.
下面我們使用快速排序法對以上數組進行排序:
<?php
$arr = Array(23,34,12,56,43,98,89);
function quick($arr){
$left = array();
$right = array();
if(count($arr)<=1){
return $arr;
}
for($i=1;$i<count($arr);$i++){
if($arr[0]>$arr[$i]){
$left[] = $arr[$i];
}else{
$right[] = $arr[$i];
}
}
$left = quick($left);
$right = quick($right);
return array_merge($left,array($arr[0]),$right);
}
?>
所謂快速排序,就是在$arr數組中任意取一個值作為中間值,然後將這個值與數組內其他所有元素相比較,比這個值小的放到左邊,比這個值大的放到這個值的右邊, 此時完成一趟排序.以此類推,再將這個值左邊的數進行上述排序,同樣對右邊的數進行上述排序.直到將所有的值都比較完.
我們來看上面的代碼:
首先使用快速排序的理念就需要使用遞歸,說到遞歸,就是用函數自己調用自己,逐層深入,最後將拿到的值返回的思想.
下面我們來看,首先我們需要自定義一個函數quick(),讓此函數自己調用自己.
這裡中間值我們用$arr[0],這個是隨意取的,不是必須的,
為了讓大家思路清晰,我們先定義兩個空數組,就相當於兩個杯子,
讓$arr[0]與數組內所有的值進行比較,比$arr[0]小的值放到第一個杯子中,比$arr[0]大的放到第二個杯子中,在程序中分別為$left和$right,
我們判斷,如果給定的數組元素只有一個或為空,此數組將被quick函數返回,不再執行下面的內容,
接下來我們對數組進行遍歷,並用遍歷出來的值分別與$arr[0]進行比較,比$arr[0]小的值存入$left數組,比$arr[0]大的的值存入$right數組,此時完成一趟排序,
接下來再對$left數組和$right數組進行同樣的操作,也就是調用函數自己,將$left數組和$right數組傳入,直到$left數組或$right數組的數組元素為一個時,不再調用自己,直接返回,
最後將左邊的數組,$arr[0],$right數組合並,即可得到最終的排序結果.
修正:
糾正效率方面的問題,在測試效率的時候,發生一個錯誤,導致效率測試不准確,經各位同學提醒,又一再測試,最終發現對此數組排序時運用快速排序的運算效率與冒泡排序的第二種相差不多,但是冒泡的第一種還是要比第二種明顯的高一些,這個測試結果只能作為參考,要精確地算出每種算法的效率,需要對算法內部進行排序次數的統計.
再次感謝各位同學的關注,以及對於此問題的糾正,這是一個開放的平台,請大家暢所欲言,多多交流,共同進步...
摘自 zdrjlamp
