php中實(shí)現(xiàn)快速排序的方法-創(chuàng)新互聯(lián)

php中實(shí)現(xiàn)快速排序的方法？很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

10年積累的成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有上林免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

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

復(fù)制代碼 代碼如下:

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);
}

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

復(fù)制代碼 代碼如下:

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);
}

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

如果沒有交叉著交換兩邊值，繼續(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次交互的額外開銷。該題還有另外兩個(gè)考點(diǎn)，針對(duì)死記硬背的同學(xué)：

1：中間的兩個(gè)while可否互換。當(dāng)然不能互換，因?yàn)閷?duì)于快盤需要一個(gè)額外的空間保存初始的左值，這樣左右互換的時(shí)候，先用右邊覆蓋已經(jīng)保存

為中值的左值，否則會(huì)出現(xiàn)問題。見這句$array[$left] = $array[$right];

2：$array[$right] = $key; 該語句含義可否省略。該句不能省略，大家可以考慮一個(gè)極端情況比如兩個(gè)值的排序（5,2），逐步看下就明白了。

復(fù)制代碼 代碼如下:

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);
}

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司，的支持。

本文名稱：php中實(shí)現(xiàn)快速排序的方法-創(chuàng)新互聯(lián)
當(dāng)前鏈接：http://bm7419.com/article28/dgdicp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計(jì)公司、微信公眾號(hào)、App開發(fā)、定制開發(fā)、企業(yè)建站、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)