찾다
백엔드 개발PHP 튜토리얼php项目开发中用到的快速排序算法分析,项目开发算法分析_PHP教程

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

本文实例讲述了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组里面的所有人身高都要 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;
 }
}

不正确之处,欢迎指正!

代码备份:

<&#63;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操作office文档技巧总结(包括word,excel,access,ppt)》、《PHP数组(Array)操作技巧大全》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php正则表达式用法总结》、及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1138978.htmlTechArticlephp项目开发中用到的快速排序算法分析,项目开发算法分析 本文实例讲述了php项目开发中用到的快速排序算法。分享给大家供大家参考,具...
성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
PHP 세션이 실패 할 수있는 몇 가지 일반적인 문제는 무엇입니까?PHP 세션이 실패 할 수있는 몇 가지 일반적인 문제는 무엇입니까?Apr 25, 2025 am 12:16 AM

phpsession 실패 이유에는 구성 오류, 쿠키 문제 및 세션 만료가 포함됩니다. 1. 구성 오류 : 올바른 세션을 확인하고 설정합니다. 2. 쿠키 문제 : 쿠키가 올바르게 설정되어 있는지 확인하십시오. 3. 세션 만료 : 세션 시간을 연장하기 위해 세션을 조정합니다 .GC_MAXLIFETIME 값을 조정하십시오.

PHP의 세션 관련 문제를 어떻게 디버그합니까?PHP의 세션 관련 문제를 어떻게 디버그합니까?Apr 25, 2025 am 12:12 AM

PHP에서 세션 문제를 디버그하는 방법 : 1. 세션이 올바르게 시작되었는지 확인하십시오. 2. 세션 ID의 전달을 확인하십시오. 3. 세션 데이터의 저장 및 읽기를 확인하십시오. 4. 서버 구성을 확인하십시오. 세션 ID 및 데이터를 출력, 세션 파일 컨텐츠보기 등을 통해 세션 관련 문제를 효과적으로 진단하고 해결할 수 있습니다.

session_start ()가 여러 번 호출되면 어떻게됩니까?session_start ()가 여러 번 호출되면 어떻게됩니까?Apr 25, 2025 am 12:06 AM

Session_Start ()로 여러 통화를하면 경고 메시지와 가능한 데이터 덮어 쓰기가 발생합니다. 1) PHP는 세션이 시작되었다는 경고를 발행합니다. 2) 세션 데이터의 예상치 못한 덮어 쓰기를 유발할 수 있습니다. 3) Session_status ()를 사용하여 반복 통화를 피하기 위해 세션 상태를 확인하십시오.

PHP에서 세션 수명을 어떻게 구성합니까?PHP에서 세션 수명을 어떻게 구성합니까?Apr 25, 2025 am 12:05 AM

SESSION.GC_MAXLIFETIME 및 SESSION.COOKIE_LIFETIME을 설정하여 PHP에서 세션 수명을 구성 할 수 있습니다. 1) SESSION.GC_MAXLIFETIME 서버 측 세션 데이터의 생존 시간을 제어합니다. 2) 세션 .Cookie_Lifetime 클라이언트 쿠키의 수명주기를 제어합니다. 0으로 설정하면 브라우저가 닫히면 쿠키가 만료됩니다.

세션을 저장하기 위해 데이터베이스를 사용하면 어떤 장점이 있습니까?세션을 저장하기 위해 데이터베이스를 사용하면 어떤 장점이 있습니까?Apr 24, 2025 am 12:16 AM

데이터베이스 스토리지 세션 사용의 주요 장점에는 지속성, 확장 성 및 보안이 포함됩니다. 1. 지속성 : 서버가 다시 시작 되더라도 세션 데이터는 변경되지 않아도됩니다. 2. 확장 성 : 분산 시스템에 적용하여 세션 데이터가 여러 서버간에 동기화되도록합니다. 3. 보안 : 데이터베이스는 민감한 정보를 보호하기 위해 암호화 된 스토리지를 제공합니다.

PHP에서 사용자 정의 세션 처리를 어떻게 구현합니까?PHP에서 사용자 정의 세션 처리를 어떻게 구현합니까?Apr 24, 2025 am 12:16 AM

SessionHandlerInterface 인터페이스를 구현하여 PHP에서 사용자 정의 세션 처리 구현을 수행 할 수 있습니다. 특정 단계에는 다음이 포함됩니다. 1) CustomsessionHandler와 같은 SessionHandlerInterface를 구현하는 클래스 만들기; 2) 인터페이스의 방법 (예 : Open, Close, Read, Write, Despare, GC)의 수명주기 및 세션 데이터의 저장 방법을 정의하기 위해 방법을 다시 작성합니다. 3) PHP 스크립트에 사용자 정의 세션 프로세서를 등록하고 세션을 시작하십시오. 이를 통해 MySQL 및 Redis와 같은 미디어에 데이터를 저장하여 성능, 보안 및 확장 성을 향상시킬 수 있습니다.

세션 ID 란 무엇입니까?세션 ID 란 무엇입니까?Apr 24, 2025 am 12:13 AM

SessionId는 웹 애플리케이션에 사용되는 메커니즘으로 사용자 세션 상태를 추적합니다. 1. 사용자와 서버 간의 여러 상호 작용 중에 사용자의 신원 정보를 유지하는 데 사용되는 무작위로 생성 된 문자열입니다. 2. 서버는 쿠키 또는 URL 매개 변수를 통해 클라이언트로 생성하여 보낸다. 3. 생성은 일반적으로 임의의 알고리즘을 사용하여 독창성과 예측 불가능 성을 보장합니다. 4. 실제 개발에서 Redis와 같은 메모리 내 데이터베이스를 사용하여 세션 데이터를 저장하여 성능 및 보안을 향상시킬 수 있습니다.

무국적 환경 (예 : API)에서 세션을 어떻게 처리합니까?무국적 환경 (예 : API)에서 세션을 어떻게 처리합니까?Apr 24, 2025 am 12:12 AM

JWT 또는 쿠키를 사용하여 API와 같은 무국적 환경에서 세션을 관리 할 수 ​​있습니다. 1. JWT는 무국적자 및 확장 성에 적합하지만 빅 데이터와 관련하여 크기가 크다. 2. 쿠키는보다 전통적이고 구현하기 쉽지만 보안을 보장하기 위해주의해서 구성해야합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse를 SAP NetWeaver 애플리케이션 서버와 통합합니다.

WebStorm Mac 버전

WebStorm Mac 버전

유용한 JavaScript 개발 도구

SublimeText3 Linux 새 버전

SublimeText3 Linux 새 버전

SublimeText3 Linux 최신 버전

MinGW - Windows용 미니멀리스트 GNU

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.