萬盛學電腦網

 萬盛學電腦網 >> 網絡編程 >> 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);

}

 

copyright © 萬盛學電腦網 all rights reserved