PHP遞歸實(shí)現(xiàn)快速排序的方法示例

本文實(shí)例講述了PHP遞歸實(shí)現(xiàn)快速排序的方法。分享給大家供大家參考，具體如下：

首先我們要理解一下快速排序的原理：找到當(dāng)前數(shù)組中的任意一個(gè)元素（一般選擇第一個(gè)元素），作為標(biāo)準(zhǔn)，新建兩個(gè)空數(shù)組，遍歷整個(gè)數(shù)組元素，如果遍歷到的元素比當(dāng)前的元素要小，那么就放到左邊的數(shù)組，否則放到右面的數(shù)組，然后再對(duì)新數(shù)組進(jìn)行同樣的操作。

不難發(fā)現(xiàn)，這里符合遞歸的原理，所以我們可以用遞歸來(lái)實(shí)現(xiàn)。

使用遞歸，則需要找到遞歸點(diǎn)和遞歸出口：

遞歸點(diǎn)：如果數(shù)組的元素大于1，就需要再進(jìn)行分解，所以我們的遞歸點(diǎn)就是新構(gòu)造的數(shù)組元素個(gè)數(shù)大于1

遞歸出口：我們什么時(shí)候不需要再對(duì)新數(shù)組不進(jìn)行排序了呢？就是當(dāng)數(shù)組元素個(gè)數(shù)變成1的時(shí)候，所以這就是我們的出口。

理解了原理，來(lái)看一下代碼實(shí)現(xiàn)~

?php
//快速排序
//待排序數(shù)組
$arr=array(6,3,8,6,4,2,9,5,1);
//函數(shù)實(shí)現(xiàn)快速排序
function quick_sort($arr)
{
    //判斷參數(shù)是否是一個(gè)數(shù)組
    if(!is_array($arr)) return false;
    //遞歸出口:數(shù)組長(zhǎng)度為1，直接返回?cái)?shù)組
    $length=count($arr);
    if($length=1) return $arr;
    //數(shù)組元素有多個(gè),則定義兩個(gè)空數(shù)組
    $left=$right=array();
    //使用for循環(huán)進(jìn)行遍歷，把第一個(gè)元素當(dāng)做比較的對(duì)象
    for($i=1;$i$length;$i++)
    {
      //判斷當(dāng)前元素的大小
      if($arr[$i]$arr[0]){
        $left[]=$arr[$i];
      }else{
        $right[]=$arr[$i];
      }
    }
    //遞歸調(diào)用
    $left=quick_sort($left);
    $right=quick_sort($right);
    //將所有的結(jié)果合并
    return array_merge($left,array($arr[0]),$right);
}
//調(diào)用
echo "pre>";
print_r(quick_sort($arr));

運(yùn)行結(jié)果：

Array
(
  [0] => 1
  [1] => 2
  [2] => 3
  [3] => 4
  [4] => 5
  [5] => 6
  [6] => 6
  [7] => 8
  [8] => 9
)

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動(dòng)畫(huà)演示插入/選擇/冒泡/歸并/希爾/快速排序算法過(guò)程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《php排序算法總結(jié)》、《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《php字符串(string)用法總結(jié)》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》

希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。