php實現(xiàn)快速排序的方法：首先創(chuàng)建一個PHP示例文件；然后創(chuàng)建交換函數(shù)和主函數(shù)；接著對低子表和高子表進(jìn)行遞歸排序；最后調(diào)用QuickSort算法即可。

推薦：《PHP視頻教程》

基本思想：

快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。他的基本思想是：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以達(dá)到整個序列有序的目的。

基本算法步驟：

舉個栗子：

假如現(xiàn)在待排序記錄是：

6   2   7   3   8   9

第一步、創(chuàng)建變量 $low 指向記錄中的第一個記錄，$high 指向最后一個記錄，$pivot 作為樞軸賦值為待排序記錄的第一個元素（不一定是第一個），這里：

$low = 0; $high = 5; $pivot = 6;

第二步、我們要把所有比 $pivot 小的數(shù)移動到 $pivot 的左面，所以我們可以開始尋找比6小的數(shù)，從 $high 開始，從右往左找，不斷遞減變量 $high 的值，我們找到第一個下標(biāo) 3 的數(shù)據(jù)比 6 小，于是把數(shù)據(jù) 3 移到下標(biāo) 0 的位置（$low 指向的位置），把下標(biāo) 0 的數(shù)據(jù) 6 移到下標(biāo) 3，完成第一次比較：

3   2   7   6   8   9  //這時候,$high 減小為 3 $low = 0; $high = 3; $pivot = 6;

第三步、我們開始第二次比較，這次要變成找比 $pivot 大的了，而且要從前往后找了。遞加變量 $low，發(fā)現(xiàn)下標(biāo) 2 的數(shù)據(jù)是第一個比 $pivot 大的，于是用下標(biāo) 2 （$low 指向的位置）的數(shù)據(jù) 7 和 指向的下標(biāo) 3 （$high 指向的位置）的數(shù)據(jù)的 6 做交換，數(shù)據(jù)狀態(tài)變成下表：

3   2   6   7   8   9  //這時候,$high 減小為 3 $low = 2; $high = 3; $pivot = 6;

完成第二步和第三步我們稱為完成一個循環(huán)。

第四步（也就是開啟下一個循環(huán)）、模仿第二步的過程執(zhí)行。
第五步、模仿第三步的過程執(zhí)行。

執(zhí)行完第二個循環(huán)之后，數(shù)據(jù)狀態(tài)如下：

3   2   6   7   8   9  //這時候,$high 減小為 3 $low = 2; $high = 2; $pivot = 6;

到了這一步，我們發(fā)現(xiàn) $low 和 $high“碰頭”了：他們都指向了下標(biāo) 2。于是，第一遍比較結(jié)束。得到結(jié)果如下，凡是 $pivot(=6) 左邊的數(shù)都比它小，凡是 $pivot 右邊的數(shù)都比它大。

然后，對 、$pivot 兩邊的數(shù)據(jù) {3，2} 和 {7，8，9}，再分組分別進(jìn)行上述的過程，直到不能再分組為止。

注意：第一遍快速排序不會直接得到最終結(jié)果，只會把比k大和比k小的數(shù)分到k的兩邊。為了得到最后結(jié)果，需要再次對下標(biāo)2兩邊的數(shù)組分別執(zhí)行此步驟，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個數(shù)據(jù)），才能得到正確結(jié)果。

算法實現(xiàn)：

//交換函數(shù) function swap(array &$arr,$a,$b){     $temp = $arr[$a];     $arr[$a] = $arr[$b];     $arr[$b] = $temp; }  //主函數(shù)： function QuickSort(array &$arr){     $low = 0;     $high = count($arr) - 1;     QSort($arr,$low,$high); }

主函數(shù)中，由于第一遍快速排序是對整個數(shù)組排序的，因此開始是 $low=0,$high=count($arr)-1。
然后 QSort() 函數(shù)是個遞歸調(diào)用過程，因此對它封裝了一下：

function QSort(array &$arr,$low,$high){     //當(dāng) $low >= $high 時表示不能再進(jìn)行分組，已經(jīng)能夠得出正確結(jié)果了     if($low < $high){         $pivot = Partition($arr,$low,$high);  //將$arr[$low...$high]一分為二，算出樞軸值         QSort($arr,$low,$pivot - 1);	//對低子表（$pivot左邊的記錄）進(jìn)行遞歸排序         QSort($arr,$pivot + 1,$high);	//對高子表（$pivot右邊的記錄）進(jìn)行遞歸排序     } }

從上面的 QSort（）函數(shù)中我們看出，Partition（）函數(shù)才是整段代碼的核心，因為該函數(shù)的功能是：選取當(dāng)中的一個關(guān)鍵字，比如選擇第一個關(guān)鍵字。然后想盡辦法將它放到某個位置，使得它左邊的值都比它小，右邊的值都比它大，我們將這樣的關(guān)鍵字成為樞軸（pivot）。

直接上代碼：

//選取數(shù)組當(dāng)中的一個關(guān)鍵字，使得它處于數(shù)組某個位置時，左邊的值比它小，右邊的值比它大，該關(guān)鍵字叫做樞軸 //使樞軸記錄到位，并返回其所在位置 function Partition(array &$arr,$low,$high){     $pivot = $arr[$low];   //選取子數(shù)組第一個元素作為樞軸     while($low < $high){  //從數(shù)組的兩端交替向中間掃描（當(dāng) $low 和 $high 碰頭時結(jié)束循環(huán)）         while($low < $high && $arr[$high] >= $pivot){             $high --;         }         swap($arr,$low,$high);	//終于遇到一個比$pivot小的數(shù)，將其放到數(shù)組低端          while($low < $high && $arr[$low] <= $pivot){             $low ++;         }         swap($arr,$low,$high);	//終于遇到一個比$pivot大的數(shù)，將其放到數(shù)組高端     }     return $low;   //返回high也行，畢竟最后low和high都是停留在pivot下標(biāo)處 }

組合起來的整個代碼如下：

function swap(array &$arr,$a,$b){     $temp = $arr[$a];     $arr[$a] = $arr[$b];     $arr[$b] = $temp; }  function Partition(array &$arr,$low,$high){     $pivot = $arr[$low];   //選取子數(shù)組第一個元素作為樞軸     while($low < $high){  //從數(shù)組的兩端交替向中間掃描         while($low < $high && $arr[$high] >= $pivot){             $high --;         }         swap($arr,$low,$high);	//終于遇到一個比$pivot小的數(shù)，將其放到數(shù)組低端         while($low < $high && $arr[$low] <= $pivot){             $low ++;         }         swap($arr,$low,$high);	//終于遇到一個比$pivot大的數(shù)，將其放到數(shù)組高端     }     return $low;   //返回high也行，畢竟最后low和high都是停留在pivot下標(biāo)處 }  function QSort(array &$arr,$low,$high){     if($low < $high){         $pivot = Partition($arr,$low,$high);  //將$arr[$low...$high]一分為二，算出樞軸值         QSort($arr,$low,$pivot - 1);   //對低子表進(jìn)行遞歸排序         QSort($arr,$pivot + 1,$high);  //對高子表進(jìn)行遞歸排序     } }  function QuickSort(array &$arr){     $low = 0;     $high = count($arr) - 1;     QSort($arr,$low,$high); }

我們調(diào)用算法：

$arr = array(9,1,5,8,3,7,4,6,2); QuickSort($arr); var_dump($arr);

復(fù)雜度分析：

在最優(yōu)的情況下，也就是選擇數(shù)軸處于整個數(shù)組的中間值的話，則每一次就會不斷將數(shù)組平分為兩半。因此最優(yōu)情況下的時間復(fù)雜度是 O(nlogn) （跟堆排序、歸并排序一樣）。

最壞的情況下，待排序的序列是正序或逆序的，那么在選擇樞軸的時候只能選到邊緣數(shù)據(jù)，每次劃分得到的比上一次劃分少一個記錄，另一個劃分為空，這樣的情況的最終時間復(fù)雜度為 O(n^2).

綜合最優(yōu)與最差情況，平均的時間復(fù)雜度是 O(nlogn).

快速排序是一種不穩(wěn)定排序方法。

由于快速排序是個比較高級的排序，而且被列為20世紀(jì)十大算法之一。。。。如此牛掰的算法，我們還有什么理由不去學(xué)他呢！

盡管這個算法已經(jīng)很牛掰了，但是上面的算法程序依然有改進(jìn)的地方。