开发者社区> wangtaotao> 正文

开发中用到的一个快速排序法

简介:     实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算法),另外,每种语言,比如java,php都或多或少已经封装好排序函数给程序员使用。
+关注继续查看

 

 

 

实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算法),另外,每种语言,比如java,php都或多或少已经封装好排序函数给程序员使用。比如有个共识,大家做web开发的基本都明白,业务逻辑多比较简单,不是很复杂的业务逻辑。我们作为web开发的程序员,基本是是web架构,对数据库增删查改数据,然后把数据展示在页面中,大多就是涉及性能优化,缓存等等。

 

学学一些常见的算法,对于实现特殊的应用还是有帮助的。比如有些时候我们依赖于数据库中order by来实现排序了,所以非常习惯直接接下交给数据库实现排序了。

接下来,我就遇到需要自己实现排序了。

 

​因为我们在实际开发中,遇到一个问题,完全需要我自己实现排序。需求如下:

 

在商品表里面,有一个字段是goods_price(商品价格),现在要开发一个促销价功能。促销价有个时间范围设置。在前台页面中,展示商品的时候。如果当前时间符合促销时间。就要按照促销价格执行。于是促销价就单独增加了一个字段来保存,叫做promote_price,促销时间配置信息比如什么时间,每天几点到几点之类的时间设置信息暂时不管,存储在其他字段中的,展示的时候,要用当前时间跟配置的时间进行比较。

单条商品展示的时候,就直接判断是否在促销时间内即可了。没遇到排序的问题。

 

而是在做商品列表页面的时候,一个这样的小细节就让我发现需求:用户可以选择商品价格按照"从高到低"也可以选择"从低到高"排序。

如果是单纯排序,以往是直接交给数据库去排序,一般我们习惯了sql中使用"order by goods_price DESC"之类的语句就能实现按照价格降序还是升序进行。

 

现在,不能简单就按照goods_price(商品价格)排序就ok。比如当前时间有的商品是符合促销时间的,那么促销价也是要作为排序的。

 

简单的 order by goods_price DESC,promote_price DESC 这种做法的话完全是不对路现在的需求。

 

所以呢,需要先对交给数据库的order by goods_price DESC 排序一次,列出数据。
然后遍历,看哪些商品数据是符合促销价格的。然后自己编写代码实现排序。
 

我初期想法是:拿到当前页的数据,里面判断每行是否符合促销价时间点

foreach(经过数据库按照价格字段排序的结果)
{
if ($v['promote_price'] > 0 && $promote_class->promtoe_validate($food_info)) {
            $v['is_promote'] = true;             $v['price']= $v['promote_price'];//将原价改为促销价显示
        }

}


//对上面的列表,因为上面的列表经过mysql排序一次后,还经过了促销价。所以还需要再次编写一个排序算法排序一次。这样就可以把促销价低的放到前面去了

 
 
 

其实,mysql数据库就是用c语言编写的。我理解数据库order by,它的排序也就是用c语言实现对数组的排序(关系表里面返回的的行列表就是一个二维数组)

 

只是,平时我们排序是交给数据库去实现了。很少自己编写,所以因为接触不多,就以为这些算法自己用不上,现在仍然需要用php语言对数据去实现排序。

 

数据库中的 order by a DESC,b ASC  的实现原理猜测?
 
第一种理解:先按照a字段进行排序。然后又对数据按照b字段进行排序。
第二种理解:先按照a字段进行排序 ,如果遇到两个值相同的,无法确定谁在前在后时,则使用b asc来确定两个数据的先后顺序。
 
我是第一种理解,后来纠正,第二种理解才是对符合对的,因为这才比较符合设计的考虑点:

为什么要设计可以多个字段进行排序?难道是为了相互覆盖掉吗?比如先按照a字段排序了。某两项数据本来是一个在前一个在后,如果又按照b asc进行排序,那么可能原来这两项数据的顺序就可能错位,就是可能导致后面的排序规则应用后的结果覆盖前面的。

 

 

假设数据库排序是这样子设计的话就没实际意义了。之所以设计多个字段进行排序。就是为了解决,遇到两行中a字段的值都2,2的时候,怎么确定先后?这个时候就调用后面的排序规则对这两项数据排序。所以order by 后面的字段先后顺序不同造成的效果是不同的。

现实生活例子:假设要排名100个学生的英语成绩,假设排序的时候,遇到三个学生都是88分。谁排名在前呢?这个时候可以附加一种新的排序方式,对这三个学生看他们的品行分排序。这样子就好确定了。

 

 

 

 

网上的快速排序法,实现都是针对一维数组来实现的。现在我要模拟数据库中的行,也就是二维数组作为参数,并且可以指定任意字段作为排序方式。

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

 

具体,看下面

 

/*

 * 排序:此函数是一个通用函数,只要是二维数组的排序都可以调用。初衷是解决价格快速排序(涉及到促销价,无法使用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,对于排序是有影响的。结果就会影响展示效果。
*/

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
我的Java开发学习之旅------&gt;Java经典排序算法之归并排序
一、归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
1351 0
Redis开发运维实践专题功能之排序
3.1 排序 redis支持对list,set和sorted set元素的排序。排序命令是sort 完整的命令格式如下: + SORT key [BY pattern] [LIMIT start count] [GET pattern] [ASC|DESC] [ALPHA] [STORE dstkey] 复杂度为O(N+M*log(M))。
1195 0
我的Java开发学习之旅------&gt;Java经典排序算法之希尔排序
一、希尔排序(Shell Sort) 希尔排序(Shell Sort)是一种插入排序算法,因D.L.Shell于1959年提出而得名。 Shell排序又称作缩小增量排序。
1102 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
28325 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22193 0
我的Java开发学习之旅------&gt;Java经典排序算法之二分插入排序
一、折半插入排序(二分插入排序) 将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。在处理A[i]时,A[0]……A[i-1]已经按关键码值排好序。
1184 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20290 0
+关注
wangtaotao
专注于互联网系统设计
167
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载