php 四種基本排序演算法

冒泡排序

　　思路分析：法如其名，就是像冒泡一樣，每次從數組當中 冒一個最大的數出來。

　　第一輪：從第一個到最後一個冒泡比較，運行結果：最後一個最大

　　第二輪：從第一個到倒數第二個冒泡比較， 運行結果：最後一個最大(當前輪的最後一個)

　　以此類推...

$arr=array(1,43,54,62,21,66,32,78,36,76,39);  
function getpao($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;
} 

選擇排序

　　思路分析：每次選擇一個相應的元素，然後將其放到指定的位置

　　第一輪：從第一位開始，選擇最小的元素放在第一位（依次比較，將較小的下標存放到$p中，然後和當前位置元素交換）

　　第二輪：從第二位開始（第一位已經是最小數），選擇最小的元素放在第一位（整個數組的第二位）

　　依次類推...

function select_sort($arr) {
//實現思路 雙重迴圈完成，外層控制輪數，當前的最小值。內層 控制的比較次數
    //$i 當前最小值的位置， 需要參與比較的元素
    for($i=0, $len=count($arr); $i<$len-1; $i++) {
        //先假設最小的值的位置
        $p = $i;
        //$j 當前都需要和哪些元素比較，$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;
}

插入排序

　　思路分析：將要排序的元素插入到已經假定排序號的數組的指定位置。

　　第一輪：將第二個元素和第一個元素進行比較，如果較小，就將他們互換位置

　　第二輪：將第三個元素和第二個元素比較，若較小，則互換第三第二元素的位置；

　　　　　　將互換之後的第二個元素和第一個元素比較，若較小，則互換第二第一元素的位置

　　兩輪下來，前三個元素的大小已經排好，接下來的過程依次類推，每一輪分別和前面的所有元素進行比較，若不小於前面的元素，則不動；若小於前面某個元素，則立即互換

function insert_sort($arr) {
    //區分 哪部分是已經排序好的
    //哪部分是沒有排序的
    //找到其中一個需要排序的元素
    //這個元素 就是從第二個元素開始，到最後一個元素都是這個需要排序的元素
    //利用迴圈就可以標誌出來
    //i迴圈控制 每次需要插入的元素，一旦需要插入的元素控制好了，
    //間接已經將數組分成了2部分，下標小於當前的（左邊的），是排序好的序列
    for($i=1, $len=count($arr); $i<$len; $i++) {
        //獲得當前需要比較的元素值。
        $tmp = $arr[$i];
        //內層迴圈控制 比較 並 插入
        for($j=$i-1;$j>=0;$j--) {
   //$arr[$i];//需要插入的元素; $arr[$j];//需要比較的元素
            if($tmp < $arr[$j]) {
                //發現插入的元素要小，交換位置
                //將後邊的元素與前面的元素互換
                $arr[$j+1] = $arr[$j];
                //將前面的數設置為 當前需要交換的數
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移動的元素
           //由於是已經排序好是數組，則前面的就不需要再次比較了。
                break;
            }
        }
    }
    //將這個元素 插入到已經排序好的序列內。
    //返回
    return $arr;
}

快速排序

　　思路分析：取第一個元素為參考數，然後分別設置兩個數組，小於參考數的放在左邊數組中；大於參考數的放在右邊數組中。依次類推...（遞歸）

　　1、找到一個基準元素；

　　2、比較數組中其他所有元素；

　　3、將與基準元素比較後的結果根據大小放到兩個不同的數組中；

　　4、數組遞歸調用函數自己；

　　5、返回一個已經排好序的數組（array_merge()）

     遞歸點：數組

     遞歸出口：數組元素只有一個（或者為空）的時候

<?php

    //快速排序
    //待排序數組
    $arr = array(6,3,8,6,4,2,9,5,1);

    //函數實現快速排序
    function quick_sort($arr){
        //判斷參數是否是一個數組
        if(!is_array($arr)) return false;

        //遞歸出口：數組長度為1就直接返回數組
        $length = count($arr);
        if($length <= 1) return $arr;

        //數組元素有多個
        $left = $right = array();

        //使用for迴圈進行遍歷，把第一個元素當做比較的對象
        for($i = 1;$i < $length;$i++){
            //判斷當前元素值的大小
            if($arr[$i] < $arr[0]){
                //當前元素小於標準元素，放到左邊數組
                $left[] = $arr[$i];
            }else{
                $right[] = $arr[$i];
            }
        }

        //遞歸調用
        $left = quick_sort($left);
        $right = quick_sort($right);

        //將所有的結果合併
        return array_merge($left,array($arr[0]),$right);
    }

    echo '<pre>';
    //調用
    print_r(quick_sort($arr));

 來源：[http://www.cnblogs.com/hf8051/p/4667455.html] 感謝以上博友分享！