《PHP編程:php項目開發中用到的快速排序算法分析》要點:
本文介紹了PHP編程:php項目開發中用到的快速排序算法分析,希望對您有用。如果有疑問,可以聯系我們。
PHP編程本文實例講述了php項目開發中用到的快速排序算法.分享給大家供大家參考,具體如下:
PHP編程實際上在,做web開發,比較少遇到使用一些算法之類的,畢竟不是做搜索引擎,也不是寫底層(比如寫個類似于mysql這樣的數據庫,里面需要自己實現排序算法),另外,每種語言,比如java,php都或多或少已經封裝好排序函數給程序員使用.比如有個共識,大家做web開發的基本都明白,業務邏輯多比較簡單,不是很復雜的業務邏輯.我們作為web開發的程序員,基本是是web架構,對數據庫增刪查改數據,然后把數據展示在頁面中,大多就是涉及性能優化,緩存等等.
PHP編程學學一些常見的算法,對于實現特殊的應用還是有幫助的.比如有些時候我們依賴于數據庫中order by來實現排序了,所以非常習慣直接接下交給數據庫實現排序了.
PHP編程接下來,我就遇到需要自己實現排序了.
PHP編程?因為我們在實際開發中,遇到一個問題,完全需要我自己實現排序.需求如下:
PHP編程在商品表里面,有一個字段是goods_price(商品價格),現在要開發一個促銷價功能.促銷價有個時間范圍設置.在前臺頁面中,展示商品的時候.如果當前時間符合促銷時間.就要按照促銷價格執行.于是促銷價就單獨增加了一個字段來保存,叫做promote_price,促銷時間配置信息比如什么時間,每天幾點到幾點之類的時間設置信息暫時不管,存儲在其他字段中的,展示的時候,要用當前時間跟配置的時間進行比較.
PHP編程單條商品展示的時候,就直接判斷是否在促銷時間內即可了.沒遇到排序的問題.
PHP編程而是在做商品列表頁面的時候,一個這樣的小細節就讓我發現需求:用戶可以選擇商品價格按照"從高到低"也可以選擇"從低到高"排序.
PHP編程如果是單純排序,以往是直接交給數據庫去排序,一般我們習慣了sql中使用"order by goods_price DESC"之類的語句就能實現按照價格降序還是升序進行.
PHP編程現在,不能簡單就按照goods_price(商品價格)排序就ok.比如當前時間有的商品是符合促銷時間的,那么促銷價也是要作為排序的.
PHP編程簡單的 order by goods_price DESC,promote_price DESC 這種做法的話完全是不對路現在的需求.
PHP編程所以呢,需要先對交給數據庫的order by goods_price DESC 排序一次,列出數據.
PHP編程然后遍歷,看哪些商品數據是符合促銷價格的.然后自己編寫代碼實現排序.
PHP編程我初期想法是:拿到當前頁的數據,里面判斷每行是否符合促銷價時間點
PHP編程
foreach(經過數據庫按照價格字段排序的結果)
{
if ($v['promote_price'] > 0 && $promote_class->promtoe_validate($food_info)) {
$v['is_promote'] = true;
$v['price']= $v['promote_price'];
//將原價改為促銷價顯示
}
}
PHP編程對上面的列表,因為上面的列表經過mysql排序一次后,還經過了促銷價.所以還需要再次編寫一個排序算法排序一次.這樣就可以把促銷價低的放到前面去了
PHP編程其實,mysql數據庫就是用c語言編寫的.我理解數據庫order by,它的排序也就是用c語言實現對數組的排序(關系表里面返回的的行列表就是一個二維數組)
PHP編程只是,平時我們排序是交給數據庫去實現了.很少自己編寫,所以因為接觸不多,就以為這些算法自己用不上,現在仍然需要用php語言對數據去實現排序.
PHP編程數據庫中的 order by a DESC,b ASC? 的實現原理猜測?
PHP編程第一種理解:先按照a字段進行排序.然后又對數據按照b字段進行排序.
第二種理解:先按照a字段進行排序 ,如果遇到兩個值相同的,無法確定誰在前在后時,則使用b asc來確定兩個數據的先后順序.
PHP編程我是第一種理解,后來糾正,第二種理解才是對符合對的,因為這才比較符合設計的考慮點:
PHP編程為什么要設計可以多個字段進行排序?難道是為了相互覆蓋掉嗎?比如先按照a字段排序了.某兩項數據本來是一個在前一個在后,如果又按照b asc進行排序,那么可能原來這兩項數據的順序就可能錯位,就是可能導致后面的排序規則應用后的結果覆蓋前面的.
PHP編程假設數據庫排序是這樣子設計的話就沒實際意義了.之所以設計多個字段進行排序.就是為了解決,遇到兩行中a字段的值都2,2的時候,怎么確定先后?這個時候就調用后面的排序規則對這兩項數據排序.所以order by 后面的字段先后順序不同造成的效果是不同的.
PHP編程現實生活例子:假設要排名100個學生的英語成績,假設排序的時候,遇到三個學生都是88分.誰排名在前呢?這個時候可以附加一種新的排序方式,對這三個學生看他們的品行分排序.這樣子就好確定了.
PHP編程網上的快速排序法,實現都是針對一維數組來實現的.現在我要模擬數據庫中的行,也就是二維數組作為參數,并且可以指定任意字段作為排序方式.
PHP編程比如從數據庫中查詢出一個數據列表,原封不動的對這個列表可以指定某個字段進行排序(數據庫就是實現這個需求吧.當然他們要先進得些.人家牛逼些 呵呵.
PHP編程具體,看下面:
PHP編程
/*
* 排序:此函數是一個通用函數,只要是二維數組的排序都可以調用.初衷是解決價格快速排序(涉及到促銷價,無法使用order by解決)
* +--------------------------------------------------------------------------
* @param $arr 要排序的數組,二維數組.對應就是數據庫中的多行數據 array(
* 0=>array("字段1"=>'','字段2'=>''...)
* 1=>array("字段1"=>'','字段2'=>''...)
* 2=>array("字段1"=>'','字段2'=>''...)
* )
* +--------------------------------------------------------------------------
* @param $key_field 按照哪個字段進行排序,不要傳入一個并不存在的字段.會打亂原來的順序
* +--------------------------------------------------------------------------
* @param $sort_type = asc or desc 排序方式.從小大到大,還是從大到小
*/
function quickSort($arr, $key_field, $sort_type = "asc") {
if (count($arr) > 1) {
//使用哪個字段排序,先得到該字段所有數據,目的是轉換成一維數組進行排序
$key_value_arr = array();
$return_arr = array();
//先判斷排序的字段是否存在
foreach ($arr as $k => $v) {
$key_value_arr[$k] = $v[$key_field]; //得到這個字段的值
}
//php內置函數實現了按降序還是升序排,但是只支持一維數組
if ($sort_type == 'desc') {
arsort($key_value_arr);
} else {
asort($key_value_arr);
}
reset($key_value_arr);
foreach ($key_value_arr as $k => $v) {
$return_arr[$k] = $arr[$k]; //得到行
}
return $return_arr;
} else {
return $arr;
}
}
PHP編程總結一下我對快速排序法的理解
PHP編程假設有100個元素,對此進行排序.那么需要遍歷多少次呢?仍然需要遍歷至少100次.因為確實都免不了,逐個去掃描每個元素,丟到左邊,還是右邊.當第一次分割之后.還要繼續對分割后兩邊的進行重復這一步驟.
當元素數量小的時候,是體會不到區別的.如果數量很大,達到上萬個元素.需要進行排序,則需要涉及到算法了
比如比較高矮,現實中情況,我們人可以用眼睛來看,哪個更小,然后認為的排序出來.但是計算機則不同.我們必須編寫程序來告訴它要什么樣的方法實現.
PHP編程快速排序體現的思想是:分治法.分割成小塊,逐個解決.
PHP編程大體的思路描述:
PHP編程1、從一堆數據里面找到一個基準的數據.按照這個數據標準分割開來.現實例子,一堆人100個人,比較高矮.現在我找出一個高度的人,我按照這個人的身高,分成a,b兩組.比他矮的都站到a組,比他高的都站到b(跟他一樣高的隨便放哪一邊都可以),這樣子可將100個人分割成兩組人.
結果是,a組里面的所有人身高都要<=b組里面的人.
2、對a組里面的人重復第一步.對b組里面的人也重復第一步.
3、直到最后只剩下一個(因為已經沒法在繼續切割了),才分組.
PHP編程我學到一個思想:先切成大塊,然后對每個大塊單獨處理.最后把各個塊的處理結果都合并起來.
PHP編程
function quickSort($arr) {
if(count($arr) > 1) {
$k=$arr[0];
$x=array();
$y=array();
$_size=count($arr);
for($i=1;$i<$_size;$i++) {
if($arr[$i] <=$k) {
$x[] =$arr[$i];//小的放這邊
}else{
$y[] =$arr[$i];//大的放這邊.這樣子是從小到大排序,如果想從大到小返回,那么調換位置與$x[] =$arr[$i];的位置即可
}
}
//得到分割看來左右兩邊的數據
$x= quickSort($x);//左邊的數據,對這些數據再次使用分割法排序,返回的結果就是排序后的數據
$y= quickSort($y);//右邊的數據
returnarray_merge($x,array($k),$y);
}else{
return$arr;
}
}
PHP編程不正確之處,歡迎指正!
PHP編程代碼備份:
PHP編程
<?php
//大體思路:由于是二維數組.所以先得到指定key的所有值.也就是轉換為一維數組了.
/*
不過這個一維數組的key要使用二維數組的key.這樣子一維數組排序后,方便對應到二維數組中去.就是靠這個key.
一維數組如下:
array('1'=>'a','4'=>''b','3'=>'c','5'=>'d');
1,2,4這些key值,到時候就是對應到里面去的證據
思考,如果還要加一個條件呢比如像sql那樣子的:order by a,b,c
當a字段的值都相等的情況下,就啟用b字段進行排序.如果還是相等,則啟用c字段進行排序.
*/
/*
$keys = array();
$keys['gg'] = '8.9';
$keys[1] = '8.8';
$keys[5] = '7.5';
asort($keys);//排序有個特點,原來的key值不會改變的.只是把位置換一下.我之前以為是調換了key值.這樣子,0,1,2,3,4
reset($keys);
var_dump($keys);
*/
/*
* +-------------------------------------------------------
* 快速排序
* @author wangtao 2015.6.10
* +-------------------------------------------------------
* @param $arr 要排序的數組,二維數組.對應就是數據庫中的多行數據
array(
* 0=>array("字段1"=>'','字段2'=>''...)
* 1=>array("字段1"=>'','字段2'=>''...)
* 2=>array("字段1"=>'','字段2'=>''...)
* )
* @param $key_field 按照哪個字段進行排序
* @param $sort_type = asc or desc 排序方式.從小大到大,還是從大到小
* +-------------------------------------------------------
* return 按照指定排序后的一個新數組.原來的key仍然會保留
* 如:1=>array("字段1"=>'','字段2'=>''...),2=>array("字段1"=>'','字段2'=>''...)
* 按照"字段2"排序后,key為2元素可能在前面前面了,但是key值不會被修改,會原樣保留
* +-------------------------------------------------------
*/
function quick_sort($arr, $key_field, $sort_type = "asc") {
if (count($arr) > 1) {
//使用哪個字段排序,先得到該字段所有數據,目的是轉換成一維數組進行排序
$key_value_arr = array();
$return_arr = array();
//先判斷排序的字段是否存在,如果字段根本不存在,避免打亂原來數組的順序
foreach ($arr as $k => $v) {
@ $key_value_arr[$k] = $v[$key_field]; //得到這個字段的值
}
//php內置函數實現了按降序還是升序排,但是只支持一維數組
if ($sort_type == 'desc') {
arsort($key_value_arr);
} else {
asort($key_value_arr);
}
reset($key_value_arr);
foreach ($key_value_arr as $k => $v) {
$return_arr[$k] = $arr[$k]; //得到行
}
//var_dump($return_arr);
return $return_arr;
} else {
return $arr;
}
}
$array = array(
array('name'=>'手機','brand'=>'諾基亞','price'=>1050),
array('name'=>'筆記本電腦','brand'=>'lenovo','price'=>4300),
array('name'=>'剃須刀','brand'=>'飛利浦','price'=>3100),
array('name'=>'跑步機','brand'=>'三和松石','price'=>4900),
array('name'=>'手表','brand'=>'卡西歐','price'=>960),
array('name'=>'液晶電視','brand'=>'索尼','price'=>6299),
array('name'=>'激光打印機','brand'=>'惠普','price'=>1200),
array('name'=>'手機','brand'=>'諾基亞','price'=>1050),
);
var_dump(quickSort($array,'m'));
//看對一個數組里面元素值都為空的怎么排序
$row = array(
0=>null,
1=>null,
2=>null,
3=>null,
);
asort($row);
var_dump($row);//如果為空.則根據key值倒過來?
/*返回的是array
3 => null
2 => null
1 => null
0 => null
現在終于明白了,數據庫字段中是否保持null,對于排序是有影響的.結果就會影響展示效果.
*/
PHP編程更多關于PHP相關內容感興趣的讀者可查看本站專題:《php排序算法總結》、《php面向對象程序設計入門教程》、《PHP數學運算技巧總結》、《php操作office文檔技巧總結(包括word,excel,access,ppt)》、《PHP數組(Array)操作技巧大全》、《PHP數據結構與算法教程》、《php程序設計算法總結》、《php正則表達式用法總結》、及《php常見數據庫操作技巧匯總》
PHP編程希望本文所述對大家PHP程序設計有所幫助.