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/**la (3,5,8,11)lb(2,6,8,9,11,15)合併爲lc,有序排列。用php實現,不能用sort -
php實現快速排序的三種方法
三種php快速排示例,第一種效率低但最簡單最容易理解,第二個是算法導論上提供的單向一次遍歷找中值方法,第三種是雙向遍歷找中值經典快排算法。下面是小編爲大家帶來的php實現快速排序的三種方法,歡迎閱讀。 方法一:該方法 -
如何運用PHP實現字符串逆序排列
如何運用PHP實現字符串逆序排列呢?下面是小編給大家提供的實現方法,大家可以參考練習,更多詳情請關注應屆畢業生考試網。 關於字符串的逆序排列,最簡單的使用PHP函數strrev()的測試代碼如下:header('Content-type: -
如何實現PHP獲取表單數據與HTML嵌入PHP腳本
保證食品安全,保障廣大羣衆的身體健康和合法權益,下面是小編精心整理的食品安全責任書,希望能給大家帶來幫助!食品安全責任書(一)根據《中華人民共和國食品衛生法》和政府、有關部門關於食品衛生監督、管理的文件精神同 -
PHP 快速排序算法解析
快速排序之所以稱之快速是因爲冒泡排序是每次對比只交換相鄰的兩個值的位置,這樣每個值要移動到它最終的排序結果中所對應的位置,可能需要很多次位置的變化。下面小編給大家講述的是PHP 快速排序算法,歡迎閱讀,更多詳情請 -
PHP快速排序算法詳解
PHP具有非常強大的功能,所有的CGI的功能PHP都能實現,而且支持幾乎所有流行的數據庫以及操作系統。最重要的是PHP可以用C、C++進行程序的擴展!以下是小編爲大家搜索整理的PHP 快速排序算法詳解, 希望能給大家帶來幫助!更 -
PHP快速排序算法解析
天才是百分之一的靈感,百分之九十九的血汗。以下是小編爲大家搜索整理的PHP快速排序算法解析,希望能給大家帶來幫助!更多精彩內容請及時關注我們應屆畢業生考試網!快速排序算法是對冒泡算法的一個優化。他的思想是先對 -
如何加速你的PHP程序
我一直認爲PHP的運行速度是非常的理想的,尤其是Zend引擎的加速之後。但是PHP仍然有加速的可能,你知道嗎?一起來看看如何加速你的PHP程序吧。所有的一切都始於如何優化PHP的編譯嘗試使用針對CPU型號的特殊編譯參數 -msse -
分析php選擇排序法實現數組排序的方法
本文實例分析了php選擇排序法實現數組排序的.方法。分享給大家供大家參考。具體分析如下:選擇排序法的基本思路:直接用案例來說明吧,比如有一個數組$arr = array(2,6,3,9),從大到小排序。第一次大循環:它首先假設$arr[0]爲 -
淺析php如何實現App常用的秒發功能
很多社交軟件都是用了一種秒發機制,讓用戶的體檢感很好,今天我們也來談談這些社交軟件中常用的小技巧。就跟隨本站小編一起去了解下吧,想了解更多相關信息請持續關注我們應屆畢業生考試網! 前言想象一下,我們平常發朋