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實現快速排序的方法有三種,下面小編爲大家介紹php如何實現快速排序吧,歡迎大家閱讀! php如何實現快速排序 方法一:該方法比較直觀,但損失了大量的空間爲代價,使用了效率較低的merge函數。在三種方法中效率最低。 -
分析php選擇排序法實現數組排序的方法
家長會,一般是由學校或教師發起的,是學生、學生家長,以及教師間的交流、互動及介紹性的會議或活動。下面是本站小編給大家整理的英語教師九年級家長會發言稿,僅供參考。英語教師九年級家長會發言稿篇1各位家長,大家好!下面 -
php如何快速實現兩表合併並有序排列
如何快速實現兩表合併並有序排列呢?下面是小編給大家提供的代碼實例,大家可以參考閱讀,更多詳情請關注應屆畢業生考試網。具體實現方法如下:代碼如下:<?php/**la (3,5,8,11)lb(2,6,8,9,11,15)合併爲lc,有序排列。用php實現,不能用sort -
四種簡單的排序算法的php實現
許多人都說算法是程序的核心,算法的好壞決定了程序的質量。作爲一個初級phper,雖然很少接觸到算法方面的東西。但是對於基本的排序算法還是應該掌握的,它是程序開發的必備工具。這裏介紹冒泡排序,插入排序,選擇排序,快速排 -
PHP 快速排序算法解析
快速排序之所以稱之快速是因爲冒泡排序是每次對比只交換相鄰的兩個值的位置,這樣每個值要移動到它最終的排序結果中所對應的位置,可能需要很多次位置的變化。下面小編給大家講述的是PHP 快速排序算法,歡迎閱讀,更多詳情請 -
PHP快速排序算法詳解
PHP具有非常強大的功能,所有的CGI的功能PHP都能實現,而且支持幾乎所有流行的數據庫以及操作系統。最重要的是PHP可以用C、C++進行程序的擴展!以下是小編爲大家搜索整理的PHP 快速排序算法詳解, 希望能給大家帶來幫助!更 -
PHP快速排序算法解析
天才是百分之一的靈感,百分之九十九的血汗。以下是小編爲大家搜索整理的PHP快速排序算法解析,希望能給大家帶來幫助!更多精彩內容請及時關注我們應屆畢業生考試網!快速排序算法是對冒泡算法的一個優化。他的思想是先對 -
關於php堆排序實現原理與應用方法
這裏以php作爲描述語言較詳細講解堆排序原理,因保證程序可讀性,故不做優化,php程序中關於堆的一些概念如下:假設n爲當前數組的key則,n的父節點爲 n>>1 或者 n/2(整除);n的左子節點l= n<<1 或 l=n*2,n的右子節點r=(n<< -
php實時倒計時的三種實現方法實例
日子如同白駒過隙,不經意間,前方等待着我們的是新的機遇和挑戰,是時候認真思考計劃該如何寫了。計劃到底怎麼擬定才合適呢?下面是小編收集整理的學習部工作計劃9篇,希望能夠幫助到大家。學習部工作計劃 篇1 1. 做好本職工 -
PHP四種基本排序算法
各位尊敬的領導,各位親愛的同事,大家好!我叫張豔,今天我演講的題目是:愛崗敬業之青春無悔。人們用無數美好的詞句來形容美麗的青春。的確,青春充滿了理想與信念;充滿了激情與希望。我常常在想,美麗的青春到底是什麼?當我面對一