php项目开发中用到的快速排序算法分析(2)

比如从数据库中查询出一个数据列表,原封不动的对这个列表可以指定某个字段进行排序(数据库就是实现这个需求吧。当然他们要先进得些。人家牛逼些 呵呵。

具体,看下面:

/* * 排序:此函数是一个通用函数,只要是二维数组的排序都可以调用。初衷是解决价格快速排序(涉及到促销价,无法使用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; } }

总结一下我对快速排序法的理解

假设有100个元素,对此进行排序。那么需要遍历多少次呢?仍然需要遍历至少100次。因为确实都免不了,逐个去扫描每个元素,丢到左边,还是右边。当第一次分割之后。还要继续对分割后两边的进行重复这一步骤。
当元素数量小的时候,是体会不到区别的。如果数量很大,达到上万个元素。需要进行排序,则需要涉及到算法了
比如比较高矮,现实中情况,我们人可以用眼睛来看,哪个更小,然后认为的排序出来。但是计算机则不同。我们必须编写程序来告诉它要什么样的方法实现。

快速排序体现的思想是:分治法。分割成小块,逐个解决。

大体的思路描述:

1、从一堆数据里面找到一个基准的数据。按照这个数据标准分割开来。现实例子,一堆人100个人,比较高矮。现在我找出一个高度的人,我按照这个人的身高,分成a,b两组。比他矮的都站到a组,比他高的都站到b(跟他一样高的随便放哪一边都可以),这样子可将100个人分割成两组人。
结果是,a组里面的所有人身高都要<=b组里面的人。
2、对a组里面的人重复第一步。对b组里面的人也重复第一步。
3、直到最后只剩下一个(因为已经没法在继续切割了),才分组。

我学到一个思想:先切成大块,然后对每个大块单独处理。最后把各个块的处理结果都合并起来。

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 //大体思路:由于是二维数组。所以先得到指定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,对于排序是有影响的。结果就会影响展示效果。 */

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/a24d5a4b7172491d135a65bba1faa0b3.html