PHPプロジェクト開発で使用されるクイックソートアルゴリズムの解析、プロジェクト開発アルゴリズムの解析_PHPチュートリアル

PHPプロジェクト開発で使用されるクイックソートアルゴリズムの分析、プロジェクト開発アルゴリズムの分析

この記事では、PHPプロジェクト開発で使用されるクイックソートアルゴリズムを例とともに説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

実際、Web 開発を行っているときに、いくつかのアルゴリズムの使用に遭遇することは比較的まれです。結局のところ、検索エンジンを構築しているわけでも、最下層を作成しているわけでもありません (たとえば、mysql に似たデータベースを作成しているわけではありません)。さらに、Java や PHP などのすべての言語には、プログラマが使用できる多かれ少なかれカプセル化された並べ替え関数があります。たとえば、Web 開発を行う人は基本的に、ビジネス ロジックは比較的単純で、それほど複雑ではないことを理解しているというコンセンサスがあります。 Web 開発プログラマーとして、私たちは基本的に Web アーキテクチャを構築し、データベース内のデータを追加、削除、確認、変更してから、ページ上にデータを表示します。これには主にパフォーマンスの最適化、キャッシュなどが含まれます。

いくつかの一般的なアルゴリズムを学習すると、特別なアプリケーションを実装するのに役立ちます。たとえば、ソートを実装するためにデータベース内の order by に依存することがあります。そのため、ソートを実装するためにデータベースに直接渡すことに非常に慣れています。

次に、ソートを自分で実装する必要性が生じました。

実際の開発中に問題が発生したため、完全に自分でソートを実装する必要がありました。要件は次のとおりです:

product テーブルには、goods_price (製品価格) というフィールドがあります。次に、プロモーション価格関数を開発する必要があります。プロモーション価格には時間範囲設定があります。フロントページで商品を展示する際に。現在の時間がプロモーション時間と一致する場合。プロモーション価格に従ってください。そのため、プロモーション価格を保存するために、promote_price と呼ばれる別のフィールドが追加されました。毎日何時、何時、などのプロモーション時間設定情報は、他のフィールドに保存されているものは一時的に無視されます。表示時に表示される現在の時刻と設定された時刻を比較します。

単一の商品が表示されている場合は、それがプロモーション期間内であるかどうかを判断するだけです。並べ替えには問題ありません。

しかし、製品リスト ページに取り組んでいたとき、このような小さな詳細が必要性を発見しました。ユーザーは製品の価格を「高い順」または「安い順」に並べ替えることを選択できます。

単純な並べ替えの場合、以前は並べ替えのためにデータベースに直接渡されていました。一般に、SQL で「order by Goods_price DESC」などのステートメントを使用して、価格による降順または昇順を実現していました。

現在、goods_price (商品価格) で単純に並べ替えることはできません。たとえば、現時点で一部の製品がプロモーション時期と一致している場合、プロモーション価格もソートとして使用する必要があります。

goods_price DESC、promote_price DESC による単純な注文 このアプローチは、現在の需要を満たすには完全に間違っています。

そのため、最初にデータベースに送信された Goods_price DESC で注文を並べ替えて、データをリストする必要があります。

次に、どの商品データがプロモーション価格と一致するかを確認します。次に、独自のコードを記述して並べ替えを実装します。

私の最初のアイデアは、現在のページのデータを取得し、各行がプロモーション価格を満たしているかどうかを判断するというものです

リーリー

上記のリストについては、上記のリストは mysql によって一度ソートされており、プロモーション価格も超えているためです。したがって、再度並べ替えるには、並べ替えアルゴリズムを再度作成する必要があります。こうすることで、プロモーション価格が最も低いものを前面に置くことができます

実際、mysql データベースは C 言語で書かれています。データベースの並べ替えは、C言語を使用して配列を並べ替えることです(リレーショナルテーブルで返される行リストは2次元配列です)

ただ、通常は並べ替えをデータベースに任せているだけです。私は自分で書くことがほとんどないので、これらのアルゴリズムを使用することはできないと思いますが、データを並べ替えるには依然として PHP 言語を使用する必要があります。

データベース内の a DESC、b ASC による順序の実装原理を推測しますか?

最初の理解: まず、フィールドに従って並べ替えます。次に、データは b フィールドに従って並べ替えられます。
2 番目の理解: 最初に a フィールドに従って並べ替えます。同じ値が 2 つあり、どちらが最初で最後であるかを判断できない場合は、b asc を使用して 2 つのデータの順序を決定します。

最初の理解はありましたが、後から修正しました。2 番目の理解は、設計上の考慮事項とより一致しているため、より正確です。

なぜ複数のフィールドで並べ替えるように設計するのですか?お互いをカバーするためですか？たとえば、最初にフィールドで並べ替えます。ある 2 つのデータ項目が元々前と後ろにあるものを b asc に従ってソートすると、2 つのデータ項目の順序がずれる可能性があり、後のソート規則を適用した後の結果が発生する可能性があります。以前のものを上書きします。

データベースの並べ替えがこのように設計されていると仮定すると、実際的な意味はありません。並べ替え用に複数のフィールドを設計する理由。問題を解決するには、2 行の a フィールドの値が 2, 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，对于排序是有影响的。结果就会影响展示效果。
*/

更多关于PHP相关内容感兴趣的读者可查看本站专题：《php排序算法总结》、《php面向对象程序设计入门教程》、《PHP数学运算技巧总结》、《php操作office文档技巧总结(包括word,excel,access,ppt)》、《PHP数组(Array)操作技巧大全》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php正则表达式用法总结》、及《php常见数据库操作技巧汇总》

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

http://www.bkjia.com/PHPjc/1138978.htmlwww.bkjia.comtruehttp://www.bkjia.com/PHPjc/1138978.htmlTechArticlephp项目开发中用到的快速排序算法分析，项目开发算法分析 本文实例讲述了php项目开发中用到的快速排序算法。分享给大家供大家参考，具...