各種常見php排序算法
冒泡法：
這個最簡單了:
function bubble_sort($arr)
{
$n = count($arr);
for($i=0;$i<$n;$i++){
$flag = 1; //1
for($j=0;$j<$n-$i-1;$j++){
if($arr[$j] > $arr[$j+1]){
$flag = 0; //2
$tmp = $arr[$j+1];
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
}
}
if($flag) {
return $arr; //3
}
}
return $arr;
} 其中1,2,3處不是必須的，加入這個檢查是因為如果某一趟冒泡中一次也沒有交換發生，說明整個數組已經是有序的了。
插入排序
這個也比較簡單，每次處理就是將無序數列的第一個元素與有序數列的元素從后往前逐個進行比較，找出插入位置。
假設前半部分從1 ~ n -1是有序的，那么將第n項的值保存到一個臨時變量t，用這個變量與n-1比較；
如果n-1項大于t，將第n-1項移到第n項，再比較第n-2項，如果大于t移到第n-1項.........直到找到一個數(假設位置為k)小于t，將t插到這個數前面也就是K+1處。
如果n-1項小于t，那么說明1 ~ n-1項都小于n項，1 ~ n 也都是有序的。
n++ ,重復這個過程，一直到最后n為數組最后一項。
function insert_sort($arr)
{
$n = count($arr);
for($i=1;$i<$n;$i++){
$tmp = $arr[$i]; // 要插入的值
$j = $i-1;
while($j>=0){
if($arr[$j]>$tmp){
$arr[$j+1] = $arr[$j];//比要插入的值大往后移
} else {
break; // 比要插入的值小或相等 它前面也就是 $j+1處就是要插入的位置
}
$j--;
}
if($j<$i-1 ){ // 如果 $j == $i-1 說明前面都小于要插入的值，當然沒有這個判斷效果也一樣
$arr[$j+1] = $tmp;
}
}
return $arr;
}
選擇排序
每次都選擇后面最小的項和當前項交換
function select_sort($arr)
{
$n = count($arr);
for($i=0;$i<$n;$i++){
// 最小元素的值和鍵
$min = $arr[$i];
$key = $i;
for($j=$i+1;$j<$n;$j++){
if($arr[$j] < $min){
$min = $arr[$j];
$key = $j;
}
}
// 找到最小項后跟當前項交換
if($key != $i){
$tmp = $arr[$i];
$arr[$i] = $arr[$key];
$arr[$key] = $tmp;
}
}
return $arr;
}
快速排序
首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，然后對前面和后面兩個部分遞歸的進行這個過程。
每一趟的實現 把所有比關鍵數據小的數都放到它前面，所有比關鍵數據大的數都放到它后面這個效果的過程為
1.一開始操作范圍為第一個到最后一個元素，選取第一個作為關鍵數據，從后往前找到第一個比關鍵數小的數與之交換。這個位置記為 K。
2.現在關鍵數的位置變到k了，比較的方向也要改變，操作的范圍也從第二個到第K個了（因為k后面都是比關鍵數大的數了）；
然后從第二個開始往后面找到第一個比關鍵數大的數與k這個位置的關鍵數交換。這個位置記為 K2。
3.現在關鍵數的位置又變了到K2了（K2前面的都是比關鍵數小的），操作的范圍也從K2到第K-1個了，然后又回到第一步，直到操作范圍為0,；
至此終于實現比關鍵數據小的數都在他前面，比關鍵數據大的數都在它后面這個效果了，然后對前面和后面兩個部分遞歸的進行這個過程就可以得到有序的數組了。
程序如下：
function recu_fast_sort(&$arr,$start,$end)
{
$left = $i = $start; // $i記錄關鍵數的位置
$right = $end;
$flag = 0; // 記錄比較的方向
while($start < $end){
if($flag == 0 ){
if($arr[$i] > $arr[$end]){ // 找到一個比關鍵數小的數 交換
$tmp = $arr[$i];
$arr[$i] = $arr[$end];
$arr[$end] = $tmp;
$i = $end; // 新的關鍵數位置
$flag = 1; // 比較的方向改變
} else {
$end--;
}
} else {
if($arr[$i] < $arr[$start]){ // 找到一個比關鍵數大的數 交換
$tmp = $arr[$i];
$arr[$i] = $arr[$start];
$arr[$start] = $tmp;
$i = $start;
$flag = 0;
} else {
$start++;
}
}
}
if($left < $i-1){ // 遞歸前面一部分
recu_fast_sort($arr,$left,$i-1);
}
if($right > $i+1){ // 遞歸后面一部分
recu_fast_sort($arr,$i+1,$right);
}
}</pre>
// 上面是遞歸版本的下面是不遞歸的版本的，要把遞歸的改成不遞歸的，就用一個數組模擬一個隊列，把原來要遞歸的操作區域放到數組中
function fast_sort($arr)
{
$n = count($arr);
//要操作的區域放入數組
$arr_que = array(array(0,$n-1));
while(!empty($arr_que)){
// 取數組的第一項作為操作區域
$q = current($arr_que);
// 刪除這一項
array_shift($arr_que);
$left = $i = $q[0];
$right = $q[1];
$flag = 0;
while($left < $right){
if($flag == 0 ){
if($arr[$i] > $arr[$right]){
$tmp = $arr[$i];
$arr[$i] = $arr[$right];
$arr[$right] = $tmp;
$i = $right;
$flag = 1;
} else {
$right--;
}
} else {
if($arr[$i] < $arr[$left]){
$tmp = $arr[$i];
$arr[$i] = $arr[$left];
$arr[$left] = $tmp;
$i = $left;
$flag = 0;
} else {
$left++;
}
}
}
// 把新的操作區域添加到數組末尾
if($q[0] < $i-1){
array_push($arr_que,array($q[0],$i-1));
}
if($q[1]> $i+1){
array_push($arr_que,array($i+1,$q[1]));
}
}
return $arr;
}</pre>
歸并排序法（2路歸并）
歸并操作：
假設兩個數組都是有序的，那么要把這兩個數組合并成一個有序的數組，依次選取兩個數組中最小的項添加到新數組即可，因為兩個數組都是有序的
所以選取最小的從前往后選就可以了。
由于數組中的每一項都可以看做是只有一項的子數組，所以一開始每2項之間可以合并，然后再每4項，一直到整個數組只剩下兩個部分合并。
// 歸并函數：
function merger_arr(&$arr,$start,$mid,$last)
{
// 初始化兩個數組分別存放要歸并的兩個部分
$arr1 = array();
$arr2 = array();
for($i=$start;$i<=$last;$i++){
if($i<=$mid){
$arr1[] = $arr[$i];
}else{
$arr2[] = $arr[$i];
}
}
$i=0;$j=0;
$k = $start;
//兩個部分元素的個數
$n1 = $mid-$start +1;
$n2 = $last-$mid;
// 合并兩個臨時數組到原來的數組
while($i< $n1|| $j<$n2){
if($i == $n1){
$arr[$k] = $arr2[$j];
$j++;
} else if($j == $n2){
$arr[$k] = $arr1[$i];
$i++;
} else if($arr1[$i] < $arr2[$j]){
$arr[$k] = $arr1[$i];
$i++;
} else {
$arr[$k] = $arr2[$j];
$j++;
}
$k++;
}
}
// 歸并排序
function merger_sort($arr)
{
$n = count($arr);
$step = 2;// 每次歸并的項數
while($step < $n2){ // 后面一部分不一定有$step/2個元素，有可能小于$step/2，這樣最后一步$step/2一般會大于$n/2
for($i=0;$i<$n;$i=$i+$step){
$end = $i+$step > $n ? $n-1:$i+$step-1;
$mid = $i+$step/2-1;
if($mid < $end ){
// 歸并兩個部分
merger_arr($arr,$i,$mid,$end);
}
}
$step =2;
}
return $arr;
}</pre>
//上面是不遞歸的是從最小的項開始合并的，其實這個算法用遞歸寫更簡單，但是理解起來有點不直觀。
如下：
// 歸并排序
function merger_sort(&$arr,$start,$end)
{
if($start < $end){
// 把數組分為兩個部分
$i = intval(($start+$end)/2);
// 對兩個部分分別進行歸并排序
merger_sort($arr,$start,$i);
merger_sort($arr,$i+1,$end);
// 歸并兩個部分
merger_arr($arr,$start,$i,$end);
}
}
另外附二分法查找
二分法查找的前提是數組已經排好序了
function binary_search($arr,$value)
{
$n = count($arr);
if($arr[0] == $value){
return 0;
}
if($arr[$n-1] == $value){
return $n-1;
}
$left = 0;
$right = $n-1;
//要注意的是邊界，這里每次循環中 $arr[$left] 和$arr[$right]都是不可能等于$value的
while($left < $right){
$mid = intval(($left + $right)/2);
if($arr[$mid] == $value){
return $mid;
} else if($arr[$mid] > $value){
$right = $mid;
} else {
$left = $mid;
}
}
return -1;
}
來自：http://blog.csdn.net/zhaoyp1985/article/details/7200934
jopen 
openkk 
quguiliang 
yanguz123