PHP 排序算法實現講解

        所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領域得到相當地重視，尤其是在大量數據的處理方面。一個優秀的算法可以節省大量的資源。在各個領域中考慮到數據的各種限制和規范，要得到一個符合實際的優秀算法，得經過大量的推理和分析。

分別使用插入排序法，冒泡排序法，選擇排序法，快速排序法，將下面數組中的值進行按照從小到大的順序進行排序操作。

$arr(12,43,57,32,51,76,36,91,28,46,40);

1、插入排序法

分析：既定前面數字已經排好順序，現在要把第n個數字插入到前面有序的數組中，使得這n個數字也是有序的放入其中，如此反復循環直至全部排好順序。

具體代碼實現如下：

$arr(12,43,57,32,51,76,36,91,28,46,40);
function insertSort($arr) {
    $len=count($arr); 
    for($i=1, $i<$len; $i++) {
        $tmp = $arr[$i];
        for($j=$i-1;$j>=0;$j--) {
            if($tmp < $arr[$j]) {
                //比較大小當數字小時交換位置，將后面的數字與前面的數字進行互換操作
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                //不需要，直接跳過
                break;
            }
        }
    }
    return $arr;
}

2、冒泡排序法

分析：從前往后對相鄰的兩個數字依次進行比較調整，讓較大的數字往下沉，讓較小的數字往上升，即每相鄰的數字進行對比排序，順序不符合時將其調換位置。

具體代碼實現如下：

$arr(12,43,57,32,51,76,36,91,28,46,40);
function bubbleSort($arr)
{  
  $len=count($arr);
  for($i=1;$i<$len;$i++)
  { //循環比較次數
    for($k=0;$k<$len-$i;$k++)
    {
       if($arr[$k]>$arr[$k+1])
        {
            $tmp=$arr[$k+1];
            $arr[$k+1]=$arr[$k];
            $arr[$k]=$tmp;
        }
    }
  }
  return $arr;
}

3、選擇排序法

分析：選出最小的一個數字與第一個位置數字交換，之后再剩余的數當中再次找到最小的數字與第二個位置交換，依此循環到倒數第二個數字和最后一個數字比較結束為止。

具體代碼實現如下：

$arr(12,43,57,32,51,76,36,91,28,46,40);
function selectSort($arr) {
 $len=count($arr);
    for($i=0; $i<$len-1; $i++) {
        //假設最小值的位置
        $p = $i;
        for($j=$i+1; $j<$len; $j++) {
            //$arr[$p] 已知的最小值
            if($arr[$p] > $arr[$j]) {
            //比較發現更小的記錄下最小值的位置，并且在下次比較時采用已知的最小值進行比較。
                $p = $j;
            }
        }
        //確定當前最小值的位置，保存到$p中。如果發現最小值的位置與當前假設的位置$i不同，則位置互換即可。
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

4、快速排序法

分析：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

具體代碼實現如下：

$arr(12,43,57,32,51,76,36,91,28,46,40);
function quickSort($arr) {
    //判斷是否繼續進行
    $length = count($arr);
    if($length <= 1) {
        return $arr;
    }
    //選擇第一個數字作為基準
    $base_num = $arr[0];
    //遍歷除了基準外的所有數字，按照大小關系放入兩個數組內，之后初始化兩個數組
    $left_array = array();  //小于基準
    $right_array = array();  //大于基準
    for($i=1; $i<$length; $i++) {
        if($base_num > $arr[$i]) {
            //放入左邊數組
            $left_array[] = $arr[$i];
        } else {
            //放入右邊數組
            $right_array[] = $arr[$i];
        }
    }
    //分別對兩數組進行相同的排序處理方式遞歸
    $left_array = quick_sort($left_array);
    $right_array = quick_sort($right_array);
    //合并數組
    return array_merge($left_array, array($base_num), $right_array);
}