php項(xiàng)目開發(fā)中用到的快速排序算法分析

2020-03-22 19:29:35

字體：大中小

供稿：網(wǎng)友

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

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。

上一篇：PHP模擬SQL的GROUPBY算法

下一篇：PHP實(shí)現(xiàn)轉(zhuǎn)盤抽獎算法分享php實(shí)例