- 相關(guān)推薦
php實(shí)現(xiàn)快速排序的三種方法
三種php快速排示例，第一種效率低但最簡(jiǎn)單最容易理解，第二個(gè)是算法導(dǎo)論上提供的單向一次遍歷找中值方法，第三種是雙向遍歷找中值經(jīng)典快排算法。下面是小編為大家?guī)?lái)的php實(shí)現(xiàn)快速排序的三種方法，歡迎閱讀。
方法一：該方法比較直觀，但損失了大量的空間為代價(jià)，使用了效率較低的merge函數(shù)。在三種方法中效率最低。最壞情況下算法退化為(O(n*n))
代碼如下:
function quick_sort($array) {
if(count($array) <= 1) return $array;
$key = $array[0];
$rightArray = array();
$leftArray = array();
for($i = 1; $i < count($array); $i++) {
if($array[$i] >= $key) {
$rightArray[] = $array[$i];
} else {
$leftArray[] = $array[$i];
}
}
$leftArray = quick_sort($leftArray);
$rightArray = quick_sort($rightArray);
return array_merge($leftArray, array($key), $rightArray);
}
方法二：該算法來(lái)自算法導(dǎo)論，叫作Nico Lomuto方法（感興趣goole上有詳細(xì)說(shuō)明）使用最經(jīng)典的單方向一次遍歷找到中值。
但這種算法在最壞情況下（例如值相同的數(shù)組，需要n-1次劃分，每一次劃分需要O(n) 時(shí)間去掉一個(gè)元素）最壞情況下為O(n*n)
代碼如下:
function quick_sort(&$array, $start, $end) {
if ($start >= $end) return;
$mid = $start;
for ($i = $start + 1; $i <= $end; $i++) {
if ($array[$i] < $array[$mid]) {
$mid++;
$tmp = $array[$i];
$array[$i] = $array[$mid];
$array[$mid] = $tmp;
}
}
$tmp = $array[$start];
$array[$start] = $array[$mid];
$array[$mid] = $tmp;
quick_sort($array, $start, $mid - 1);
quick_sort($array, $mid + 1, $end);
}
方法三：該方法基本上是教科書式的常見(jiàn)寫法，首先從左向右遍歷小于中間元素的跳過(guò)，同時(shí)從右向左遍歷遇到大的元素跳過(guò)，然后如果沒(méi)有交叉著交換兩邊值，繼續(xù)循環(huán)，直到找到中間點(diǎn)。注意該方法在處理相同元素的時(shí)候，仍舊交換，這樣在最壞情況下也有O(nlogn)效率。但下面的函數(shù)中，如果將$array[$right] > $key 改成 $array[$right] >=$key 或?qū)?$array[$left] < $key改成$array[$left] <= $key則最壞
情況不但會(huì)墮落為O(n*n).而且除了每次比較的消耗外，還會(huì)產(chǎn)生n次交互的額外開(kāi)銷。該題還有另外兩個(gè)考點(diǎn)，針對(duì)死記硬背的同學(xué)：
1：中間的兩個(gè)while可否互換。當(dāng)然不能互換，因?yàn)閷?duì)于快盤需要一個(gè)額外的空間保存初始的左值，這樣左右互換的時(shí)候，先用右邊覆蓋已經(jīng)保存
為中值的左值，否則會(huì)出現(xiàn)問(wèn)題。見(jiàn)這句$array[$left] = $array[$right];
2：$array[$right] = $key; 該語(yǔ)句含義可否省略。該句不能省略，大家可以考慮一個(gè)極端情況比如兩個(gè)值的排序（5,2），逐步看下就明白了。
代碼如下:
function quick_sort_swap(&$array, $start, $end) {
if($end <= $start) return;
$key = $array[$start];
$left = $start;
$right = $end;
while($left < $right) {
while($left < $right && $array[$right] > $key)
$right--;
$array[$left] = $array[$right];
while($left < $right && $array[$left] < $key)
$left++;
$array[$right] = $array[$left];
}
$array[$right] = $key;
quick_sort_swap(&$array, $start, $right - 1);
quick_sort_swap(&$array, $right+1, $end);
}
【php實(shí)現(xiàn)快速排序的三種方法】相關(guān)文章：
分析php選擇排序法實(shí)現(xiàn)數(shù)組排序的方法07-19
PHP快速排序算法詳解01-26
PHP快速排序算法解析04-01
PHP 快速排序算法解析06-11
php實(shí)時(shí)倒計(jì)時(shí)的三種實(shí)現(xiàn)方法實(shí)例05-25