php如何實現快速排序

相關推薦

php如何實現快速排序

　　php實現快速排序的方法有三種，下面小編為大家介紹php如何實現快速排序吧，歡迎大家閱讀!

　　php如何實現快速排序

　　方法一：

　　該方法比較直觀，但損失了大量的空間為代價，使用了效率較低的merge函數。在三種方法中效率最低。最壞情況下算法退化為(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);

　　}

　　方法二：

　　該算法來自算法導論，叫作Nico Lomuto方法(感興趣goole上有詳細說明)使用最經典的單方向一次遍歷找到中值。

　　但這種算法在最壞情況下(例如值相同的數組，需要n-1次劃分，每一次劃分需要O(n) 時間去掉一個元素)最壞情況下為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);

　　}

　　方法三：

　　該方法基本上是教科書式的常見寫法，首先從左向右遍歷小于中間元素的跳過，同時從右向左遍歷遇到大的元素跳過，然后

　　如果沒有交叉著交換兩邊值，繼續循環，直到找到中間點。注意該方法在處理相同元素的時候，仍舊交換，這樣在最壞情況下也有O(nlogn)

　　效率。但下面的.函數中，如果將$array[$right] > $key 改成 $array[$right] >=$key 或將 $array[$left] < $key改成$array[$left] <= $key則最壞

　　情況不但會墮落為O(n*n).而且除了每次比較的消耗外，還會產生n次交互的額外開銷。該題還有另外兩個考點，針對死記硬背的同學：

　　1：中間的兩個while可否互換。當然不能互換，因為對于快盤需要一個額外的空間保存初始的左值，這樣左右互換的時候，先用右邊覆蓋已經保存

　　為中值的左值，否則會出現問題。見這句$array[$left] = $array[$right];

　　2：$array[$right] = $key; 該語句含義可否省略。該句不能省略，大家可以考慮一個極端情況比如兩個值的排序(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如何實現快速排序】相關文章：

分析php選擇排序法實現數組排序的方法07-19

php如何快速實現兩表合并并有序排列08-02

PHP中多態如何實現09-04

如何實現歸并排序10-04

快速排序算法及C#版的實現示例07-03