php如何實現快速排序
php實現快速排序的方法：首先建立一個PHP範例檔案；然後建立交換函數和主函數；接著對低子表和高子表進行遞迴排序；最後呼叫QuickSort演演算法即可。
推薦：《》
基本思想：
快速排序（Quicksort）是對氣泡排序的一種改進。他的基本思想是：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行快速排序，整個排序過程可以遞迴進行，以達到整個序列有序的目的。
基本演演算法步驟：
舉個栗子： 
假如現在待排序記錄是：
6 2 7 3 8 9
第一步、建立變數 $low 指向記錄中的第一個記錄，$high 指向最後一個記錄，$pivot 作為樞軸賦值為待排序記錄的第一個元素（不一定是第一個），這裡：
$low = 0; $high = 5; $pivot = 6;
第二步、我們要把所有比 $pivot 小的數移動到 $pivot 的左面，所以我們可以開始尋找比6小的數，從 $high 開始，從右往左找，不斷遞減變數 $high 的值，我們找到第一個下標 3 的資料比 6 小，於是把資料 3 移到下標 0 的位置（$low 指向的位置），把下標 0 的資料 6 移到下標 3，完成第一次比較：
3 2 7 6 8 9 //這時候,$high 減小為 3 $low = 0; $high = 3; $pivot = 6;
第三步、我們開始第二次比較，這次要變成找比 $pivot 大的了，而且要從前往後找了。遞加變數 $low，發現下標 2 的資料是第一個比 $pivot 大的，於是用下標 2 （$low 指向的位置）的資料 7 和 指向的下標 3 （$high 指向的位置）的資料的 6 做交換，資料狀態變成下表：
3 2 6 7 8 9 //這時候,$high 減小為 3 $low = 2; $high = 3; $pivot = 6;
完成第二步和第三步我們稱為完成一個迴圈。
第四步（也就是開啟下一個迴圈）、模仿第二步的過程執行。
第五步、模仿第三步的過程執行。
執行完第二個迴圈之後，資料狀態如下：
3 2 6 7 8 9 //這時候,$high 減小為 3 $low = 2; $high = 2; $pivot = 6;
到了這一步，我們發現 $low 和 $high「碰頭」了：他們都指向了下標 2。於是，第一遍比較結束。得到結果如下，凡是 $pivot(=6) 左邊的數都比它小，凡是 $pivot 右邊的數都比它大。
然後，對 、$pivot 兩邊的資料 {3，2} 和 {7，8，9}，再分組分別進行上述的過程，直到不能再分組為止。
注意：第一遍快速排序不會直接得到最終結果，只會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下標2兩邊的陣列分別執行此步驟，然後再分解陣列，直到陣列不能再分解為止（只有一個資料），才能得到正確結果。
演演算法實現：
//交換函數
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
//主函數：
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$low,$high);
}主函數中，由於第一遍快速排序是對整個陣列排序的，因此開始是 $low=0,$high=count($arr)-1。
然後 QSort() 函數是個遞迴呼叫過程，因此對它封裝了一下：
function QSort(array &$arr,$low,$high){
//當 $low >= $high 時表示不能再進行分組，已經能夠得出正確結果了
if($low < $high){
$pivot = Partition($arr,$low,$high); //將$arr[$low...$high]一分為二，算出樞軸值
QSort($arr,$low,$pivot - 1); //對低子表（$pivot左邊的記錄）進行遞迴排序
QSort($arr,$pivot + 1,$high); //對高子表（$pivot右邊的記錄）進行遞迴排序
}
}從上面的 QSort（）函數中我們看出，Partition（）函數才是整段程式碼的核心，因為該函數的功能是：選取當中的一個關鍵字，比如選擇第一個關鍵字。然後想盡辦法將它放到某個位置，使得它左邊的值都比它小，右邊的值都比它大，我們將這樣的關鍵字成為樞軸（pivot）。
直接上程式碼：
//選取陣列當中的一個關鍵字，使得它處於陣列某個位置時，左邊的值比它小，右邊的值比它大，該關鍵字叫做樞軸
//使樞軸記錄到位，並返回其所在位置
function Partition(array &$arr,$low,$high){
$pivot = $arr[$low]; //選取子陣列第一個元素作為樞軸
while($low < $high){ //從陣列的兩端交替向中間掃描（當 $low 和 $high 碰頭時結束迴圈）
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$low,$high); //終於遇到一個比$pivot小的數，將其放到陣列低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$low,$high); //終於遇到一個比$pivot大的數，將其放到陣列高階
}
return $low; //返回high也行，畢竟最後low和high都是停留在pivot下標處
}組合起來的整個程式碼如下：
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]; //選取子陣列第一個元素作為樞軸
while($low < $high){ //從陣列的兩端交替向中間掃描
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$low,$high); //終於遇到一個比$pivot小的數，將其放到陣列低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$low,$high); //終於遇到一個比$pivot大的數，將其放到陣列高階
}
return $low; //返回high也行，畢竟最後low和high都是停留在pivot下標處
}
function QSort(array &$arr,$low,$high){
if($low < $high){
$pivot = Partition($arr,$low,$high); //將$arr[$low...$high]一分為二，算出樞軸值
QSort($arr,$low,$pivot - 1); //對低子表進行遞迴排序
QSort($arr,$pivot + 1,$high); //對高子表進行遞迴排序
}
}
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$low,$high);
}我們呼叫演演算法：
$arr = array(9,1,5,8,3,7,4,6,2); QuickSort($arr); var_dump($arr);
複雜度分析：
在最優的情況下，也就是選擇數軸處於整個陣列的中間值的話，則每一次就會不斷將陣列平分為兩半。因此最優情況下的時間複雜度是 O(nlogn) （跟堆排序、歸併排序一樣）。
最壞的情況下，待排序的序列是正序或逆序的，那麼在選擇樞軸的時候只能選到邊緣資料，每次劃分得到的比上一次劃分少一個記錄，另一個劃分為空，這樣的情況的最終時間複雜度為 O(n^2).
綜合最優與最差情況，平均的時間複雜度是 O(nlogn).
快速排序是一種不穩定排序方法。
由於快速排序是個比較高階的排序，而且被列為20世紀十大演演算法之一。。。。如此牛掰的演演算法，我們還有什麼理由不去學他呢！
儘管這個演演算法已經很牛掰了，但是上面的演演算法程式依然有改進的地方。
以上就是php如何實現快速排序的詳細內容，更多請關注TW511.COM其它相關文章！