PHP算法——四大基础算法

2019-08-09 05:48:58来源:编程学习网 阅读 ()

新老客户大回馈,云服务器低至5折



对于大多数业务开发来说,平时很少需要自己实现数据结构与算法,都是利用已经封装好的现成接口,类库来推测、翻译业务逻辑,但是,不需要自己实现,并不代表什么都不需要了解。


如果不知道这些类库背后的原理,不懂得时间、空间复杂度分析,你如何能用好、用对它们?存储某个业务数据的时候,你如何知道应该用ArrayList,还是LinkedList呢?调用了某个函数之后,你又该如何评估代码的性能和资源的消耗?

基础架构研发工程师,写出达到开源水平的框架才是你的目标!

太深的算法就先不说,冒泡排序,选择排序,插入排序,快速排序等PHP的四大基础算法我想还是要掌握的。

冒泡排序

介绍:

冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它 重复地走访过要排序的数列,依次比较两个元素,如果他们的顺序错误就把他们交换过来 。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤:

(1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。

(2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

(3)针对所有的元素重复以上的步骤,除了最后一个。

(4)持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码示例:

//大数在前,小数在后 public function bubbleSort($arr){ $len=count($arr); //该层循环控制 需要冒泡的轮数 for($i=1;$i<$len;$i++){ //该层循环用来控制每轮 冒出一个数 需要比较的次数 for($j=0;$j<$len-$i;$j++){ //把小于号换成大于号就是,小数在前,大数在后 if($arr[$j]<$arr[$j+1]){ list($arr[$j+1],$arr[$j])=[$arr[$j],$arr[$j+1]]; } } } return $arr; }

输出结果:

//调用 $arr=array(5,2,8,1,9); $bubbleSort=$this->bubbleSort($arr); print_r($bubbleSort);die; //输出 Array ( [0] => 9 [1] => 8 [2] => 5 [3] => 2 [4] => 1 )

选择排序

介绍:

选择排序在冒泡排序的基础上进行了改进,每次通过列表时只进行一次传递交换。简单来说,选择排序的原理就是 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

步骤:

(1)先假设最小值的位置。

(2)把当前假设的值与剩下的元素做比较。

(3)比较,发现更小的,记录下最小的位置;并在下次比较的时候,采用已知的最小值最比较。

(4)如果发现,最小值的位置与当前假设的最小值的位置不同,则位置互换。反之,假设成立,当前位置保留继续往下找,直到排序完成。

代码示例:

//小数在前,大数在后 //实现思路 双重循环完成,外层控制轮数,当前的最小值。内层 控制的比较次数 public function selectSort($arr) { $len=count($arr); for($i=0;$i<$len-1;$i++){ //先假设最小值的位置 $q=$i; //当前需要和哪些元素比较 ($i 后面的) for($j=$i+1;$j<$len;$j++){ // $arr[$q] 当前已知的最小值 if($arr[$q]>$arr[$j]){ //比较,发现更小的,记录下最小的位置;并在下次比较的时候,采用已知的最小值最比较 $q=$j; } } //如果发现,最小值的位置与当前假设的位置的$i不同,则位置互换 if($q!=$i){ list($arr[$i],$arr[$q])=[$arr[$q],$arr[$i]]; } } return $arr; }

输出结果:

//调用 $arr=array(5,2,8,1,9); $selectSort=$this->selectSort($arr); print_r($selectSort);die; //输出 Array ( [0] => 1 [1] => 2 [2] => 5 [3] => 8 [4] => 9 )

插入排序

介绍:

插入排序是一种逻辑上非常好理解的排序方式,整个排序的核心就是 不断在当前已经排好部分数据的数组里,找到合适的位置插入新数据。 就像抓扑克牌,抓一张,然后再手里已经部分已经排好序的手牌的找到位置插进去。

步骤:

(1)从第一个元素开始,该元素可以认为已经被排序

(2)取出下一个元素,在已经排序的元素序列中从后向前扫描

(3)如果该元素(已排序)大于新元素,将该元素移到下一位置

(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

(5)将新元素插入到该位置中

(6)重复步骤2

代码示例:

//小数在前,大数在后 public function insertSort($arr){ $len=count($arr); //第一个元素可认定为已被排序 for($i=1;$i<$len;$i++){ //获取当前需要比较的元素值 $tmp=$arr[$i]; for ($j=$i-1; $j >=0 ; $j--) { //$tmp 需要插入的元素 $arr[$j]需要比较的元素 if($arr[$j]>$tmp){ //发现当前插入元素要小,交换位置 list($arr[$j],$arr[$j+1])=[$arr[$j+1],$arr[$j]]; } } } return $arr; }

输出结果:

//调用 $arr=array(5,2,8,1,9); $insertSort=$this->insertSort($arr); print_r($insertSort);die; //输出 Array ( [0] => 1 [1] => 2 [2] => 5 [3] => 8 [4] => 9 )

快速排序

介绍:

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

通过设置一个初始中间值,来将需要排序的数组分成3部分,小于中间值的左边,中间值,大于中间值的右边,继续递归用相同的方式来排序左边和右边,最后合并数组。

步骤:

从数列中挑出一个元素,称为 “基准”(pivot),

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码示例:

//小数在前,大数在后 public function quickSort($arr) { //判断参数是否是一个数组 if(!is_array($arr)) return false; //递归出口:数组长度为1,直接返回数组 $len=count($arr); if($len <= 1) return $arr; //数组元素有多个,则定义两个空数组 $left = $right = []; //使用for循环进行遍历,把第一个元素当做比较的对象 for($i = 1;$i < $len;$i++){ //判断当前元素的大小 if($arr[$i] > $arr[0]){ $right[] = $arr[$i]; }else{ $left[] = $arr[$i]; } } //递归调用 $left = $this->quickSort($left); $right = $this->quickSort($right); //将所有的结果合并 return array_merge($left,[$arr[0]],$right); }

输出结果:

//调用 $arr=array(5,2,8,1,9); $quickSort=$this->quickSort($arr); print_r($quickSort);die; //输出 Array ( [0] => 1 [1] => 2 [2] => 5 [3] => 8 [4] => 9 )

适用场景

利用算法的时间复杂度和空间复杂度对比分析,得出四大算法的最佳适用场景。

稳定度:意思是说原本键值一样的元素排序后相对位置不变。点击详细解释

注释:n为问题的规模,大写英文字母O为算法复杂度。

冒泡排序:当n问题的规模小时,对原本键值一样的元素排序后相对位置不变要求高时适用。

选择排序:当n问题的规模小时,对原本键值一样的元素排序后相对位置不变无要求时适用。

插入排序:在大部分已排序好的时候适用。

快速排序:当n问题的规模大时,对原本键值一样的元素排序后相对位置不变无要求时适用。


原文链接:http://www.phpxs.com/post/6399/
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:PHP后台处理语音识别

下一篇:php使用百度API实现人脸识别