php實現的常見排序算法匯總

 一、插入排序

用文字簡單的描述，比如說$arr = array(4,2,4,6,3,6,1,7,9); 這樣的一組數字進行順序排序：
那麼，首先，拿數組的第二個元素和第一元素比較，假如第一個元素大於第二元素，那麼就讓兩者位置互換，接下來，拿數組的第三個元素，分別和第二個，第一個元素比較，假如第三個元素小，那麼就互換。依次類推。這就是插入排序,它的時間頻度是：1+2+...+(n-1)=(n^2)/2。則它的時間復雜度為O(n^2).

php實現代碼如下：

01 <?php 02 function insertSort($arr){ 03    $count = count($arr); 04    if($count<2){ 05   return $arr;  06    } 07    for($i=1;$i<$count;$i++){ 08    $tmp = $arr[$i]; 09    $j=$i-1; 10    while(j>=0&&$arr[$j]<$arr[$i]){ 11   $arr[$i] = $arr[$j];            12   $arr[$j] = $tmp; 13   $j--; 14    } 15     } 16     return $arr;  17  } 18 ?>

二、選擇排序

選擇排序用語言描述的話，可以這樣,如：$arr = array(4,3,5,2,1);

首先,拿第一個和後面所有的比，找出最小的那個數字，然後和第一個數組互換（當然，如果是第一個最小，那麼就不用互換了），接著循環，即：拿第二個和後面的比較，找出最小的數字，然後和第二個數字互換，依次類推，也就是說每次都是找出剩余最小的值。 可得到：第一次，時間頻度 是n, （第一個和後面的n－1個比較，找到最小的，再看是不是第一個，不是第一個的話進行互換） 在往後，依次是 減一 。 它的時間復雜度，也是O(n^2);

php實現代碼如下：

01 <?php 02 function selectSort($arr){ 03    04    $count = count($arr); 05    if($count<2){ 06   return $arr;  07    } 08    for($i=0;$i<$count;$i++){ 09    $min=$i; 10    for(j=$i+1;$j<$count;$j++){ 11   if($arr[$min]>$arr[$j]){ 12     $min = $j; //找到最小的那個元素的下標 13   } 14    } 15    if($min!=$i){//如果下標不是$i 則互換。 16    $tmp= $arr[$i];            17     $arr[$i] = $arr[$min]; 18     $arr[$min] = $tmp; 19     } 20     } 21     return $arr;  22  } 23 ?>

三、冒泡排序  
    
冒泡排序其實上是和選擇排序相比，並無明顯差別。都是找到最小的，放到最左端。依次循環解決問題。差別在於冒泡排序的交換位置的次數較多，而選擇排序則是找到最小的元素的下標，然後直接和最左端的交換位置。

php實現代碼如下：

01 <?php 02 function selectSort($arr){ 03    04    $count = count($arr); 05    if($count<2){ 06   return $arr;  07    } 08    for($i=0;$i<$count;$i++){ 09    for(j=$i+1;$j<$count;$j++){ 10   if($arr[$i]>$arr[$j]){ 11     $tmp= $arr[$i];            12     $arr[$i] = $arr[$i]; 13     $arr[$i] = $tmp; 14   } 15    } 16     } 17     return $arr;  18  } 19 ?>

四、快速排序

快速排序，用語言來形容的話，從數組中選擇一個值$a，然後和其余元素進行比較，比$a大的放到數組right中，反之，放到數組left中。然後將left right 分別進行遞歸調用，即：再細分left right ，最後進行數組的合並。

php實現快速排序：

  01 <?php 02 function mySort($arr){ 03    04 &