寫了三種php快速排示例: 第一種效率低但最簡單最容易理解， 第二個是算法導論上提供的單向一次遍歷找中值方法， 第三種是雙向遍歷找中值經典快排算法。 三組算法實現和比較如下：

方法一：該方法比較直觀，但損失了大量的空間為代價，使用了效率較低的merge函數。在三種方法中效率最低。最壞情況下算法退化為(O(n*n))

方法二：該算法來自算法導論，叫作Nico Lomuto方法（感興趣Google上有詳細說明）使用最經典的單方向一次遍歷找到中值。 但這種算法在最壞情況下（例如值相同的數組，需要n-1次劃分，每一次劃分需要O(n) 時間去掉一個元素）最壞情況下為O(n*n)

方法三：該方法基本上是教科書式的常見寫法，首先從左向右遍歷小于中間元素的跳過，同時從右向左遍歷遇到大的元素跳過，然后如果沒有交叉則交換兩邊值，繼續循環，直到找到中間點。 注意該方法在處理相同元素的時候，仍舊交換，這樣在最壞情況下也有O(nlogn)效率。但下面的函數中，如果將$array[$right] > $key 改成 $array[$right] >=$key 或將 $array[$left] < $key改成$array[$left] <= $key則最壞情況不但會墮落為O(n*n).而且除了每次比較的消耗外，還會產生n次交互的額外開銷。該題還有另外兩個考點，針對死記硬背的同學：

原文鏈接：php實現快速排序的三種方法分享