您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

PHP常见排序算法总结

时间:2019-08-14 11:01:27  来源:  作者:

 

常见算法总结

php 算法

算法是我们遇到复杂问题时,处理程序的利器。说到算法,我们先来理解算法复杂度,其实算法复杂度是一个概念,一定程度上反映一个算法的好坏程度。算法复杂度分为两个部分,时间复杂度和空间复杂度。时间复杂度反应算法执行的时间长短,空间复杂度反应是算法占用内存(或叫存储空间)的大小。 必须说一下,所谓的复杂度,不是一个具体的值,只是一个估值,在比较两种算法优劣时使用。

1、时间复杂度

时间复杂度就是是一个函数,这个函数含有两个变量,一个算法的运行时间,一个算法要处理数据的数量。这里有一个关系:处理数据的数量越大,算法运行的次数和时间越长。假设处理数据的数量是n,算法运行的次数就是f(n)。这里的f()是一个函数,它的大小随着n增大而增大,数学上叫单调递增函数。

所以,在计算时间复杂度T(n)的时候,步骤如下: 1、先要拿出算法的基本单元。 2、根据相应的各语句确定它的执行次数f(n)。 3、找出T(n)的同数量级,将这个同数量等级赋值给f(n)。 4、因为T(n)/f(n)求极限可以得到一个常数C。(求极限值是高等数学内容,自行百度脑补一下),我们可以确定时间的复杂度T(n) = O(f(n));

总结:常用的时间复杂度所耗费的时间从小到大依次是:O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

2、空间复杂度

空间复杂度是指算法在内存内所需要的存储空间的度量,一般是指除正常占用内存开销外的辅助存储单元规模。和时间复杂度类似,这样标记:S(n)=O(f(n))。n为问题规模,f(n)为语句关于n所占存储空间的函数;

3、PHP冒泡排序法

PHP

$arr = array();
for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
} 
 $t1 = microtime(true); 
//这是一个中间变量 
$temp=0; 
//我们要把数组,从小到大排序 
//外层循环 
$flag=false;//这个优化之后效率会很高,一般够用 
for($i=0;$i<count($arr)-1;$i++){ 
 for($j=0;$j<count($arr)-1-$i;$j++){ 
 //说明前面的数比后面的数大,就要交换 
 if($arr[$j]>$arr[$j+1]){ 
 $temp=$arr[$j]; 
 $arr[$j]=$arr[$j+1]; 
 $arr[$j+1]=$temp; 
 $flag=true; 
 } 
 } 
 if(!$flag){ 
 //已经是有序了 
 break; 
 } 
 $flag=false; 
} 
$t2 = microtime(true); 
echo $t2 -$t1;

算法部分代码平均运行时间(php 5.6): 11.246428012848 冒泡算法的平均时间复杂度为:O(n2)

4、PHP选择排序法

选择排序法思路: 每次选择一个相应的元素,然后将其放到指定的位置

PHP

//实现思路 双重循环完成,外层控制轮数,当前的最小值。内层 控制的比较次数 
$arr=array(); 
for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
} 
$t1 = microtime(true); 
//这是一个中间变量 
$temp=0; 
for($i=0;$i<count($arr)-1;$i++){ 
 //假设$i就是最小的数 是需要参与比较的元素
 $minVal=$arr[$i]; 
 //记录我认为的最小数的下标 
 $minIndex=$i; 
 for($j=$i+1;$j<count($arr);$j++){ 
 //说明我们认为的最小值,不是最小 
 if($minVal>$arr[$j]){ 
 $minVal=$arr[$j]; 
 $minIndex=$j; 
 } 
 } 
 //最后交换 
 $temp=$arr[$i]; 
 $arr[$i]=$arr[$minIndex]; 
 $arr[$minIndex]=$temp; 
} 
$t2 = microtime(true); 
echo $t2 -$t1; 

算法部分代码平均运行时间 6.1832849979401 快速排序法平均时间复杂度:O(n2)

5、插入排序法(小到大排序)

效率又比 选择排序法要高一些 插入排序法思路:将要排序的元素插入到已经 假定排序号的数组的指定位置

PHP

 $arr=array(); 
 for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
 } 
 $t1 = microtime(true); 
 //先默认下标为0的这个数已经是有序 
 for($i=1;$i<count($arr);$i++){ 
 //$insertVal是准备插入的数 
 $insertVal=$arr[$i]; 
 //准备先和谁下标为$inserIndex的比较 
 $inserIndex=$i-1; 
 //如果这个条件满足,说明我们还没有找到适当的位置 
 while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){ 
 //同时把数后移 
 $arr[$inserIndex+1] = $arr[$inserIndex]; 
 $inserIndex--; 
 } 
 //插入(这时就给$inserIndex找到适当的位置) 
 $arr[$inserIndex+1] = $insertVal; 
 } 
 $t2 = microtime(true); 
 echo $t2 -$t1; 

算法部分代码平均运行时间 2.6323339939117 插入法的平均时间复杂度:O(n2)

6、快速排序法

PHP

$arr=array(); 
for($i=0;$i<10000;$i++){ 
 $arr[] = mt_rand(1,100000); 
} 
$t1 = microtime(true); 
$a = quick_sort($arr);
$t2 = microtime(true); 
echo $t2 -$t1;
function quick_sort($arr) { 
 //先判断是否需要继续进行 
 $length = count($arr); 
 if($length <= 1) { 
 return $arr; 
 } 
 //如果没有返回,说明数组内的元素个数 多余1个,需要排序 
 //选择一个标尺 
 //选择第一个元素 
 $base_num = $arr[0]; 
 //遍历 除了标尺外的所有元素,按照大小关系放入两个数组内 
 //初始化两个数组 
 $left_array = array();//小于标尺的 
 $right_array = array();//大于标尺的 
 for($i=1; $i<$length; $i++) { 
 if($base_num > $arr[$i]) { 
 //放入左边数组 
 $left_array[] = $arr[$i]; 
 } else { 
 //放入右边 
 $right_array[] = $arr[$i]; 
 } 
 } 
 //再分别对 左边 和 右边的数组进行相同的排序处理方式 
 //递归调用这个函数,并记录结果 
 $left_array = quick_sort($left_array); 
 $right_array = quick_sort($right_array); 
 //合并左边 标尺 右边 
 return array_merge($left_array, array($base_num), $right_array); 
}

算法部分代码平均运行时间 0.055506944656372 快速排序法的平均时间复杂度:O(n*log2n)



Tags:排序算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 排序算法  点击:(16)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 排序算法  点击:(40)  评论:(0)  加入收藏
1. 插入排序步骤:1.从第一个元素开始,该元素可以认为已经被排序2.取下一个元素tem,从已排序的元素序列从后往前扫描3.如果该元素大于tem,则将该元素移到下一位4.重复步骤3,直到找...【详细内容】
2021-08-19  Tags: 排序算法  点击:(100)  评论:(0)  加入收藏
人生有涯,学海无涯今天跟大家分享一个常用的排序算法&mdash;&mdash;快速排序。我想大家在日常的工作或者面试的时候肯定经常会遇到很多排序算法,而且快速排序算法往往是这里面...【详细内容】
2021-03-04  Tags: 排序算法  点击:(182)  评论:(0)  加入收藏
1. 冒泡排序算法实现(javascript)//冒泡排序算法(javascript)//author:Hengda//arr数组//mode false 升序 ture 降序function bubbleSort( arr, mode ){ var i, j, temp, l...【详细内容】
2021-02-07  Tags: 排序算法  点击:(220)  评论:(0)  加入收藏
用希尔排序法对一组数据由小到大进行排序,数据分别为 69、56、12、136、3、55、46、 99、88、25。例子:(1)自定义函数 shsort(),实现希尔排序。(2) main() 函数作为程序的入口...【详细内容】
2021-01-25  Tags: 排序算法  点击:(216)  评论:(0)  加入收藏
选择排序 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续...【详细内容】
2020-11-19  Tags: 排序算法  点击:(173)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。0...【详细内容】
2020-07-26  Tags: 排序算法  点击:(97)  评论:(0)  加入收藏
今天我们就来讨论面试官最喜欢问到的排序算法吧,从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手,彻底搞清实现原理,保证面试道路一路畅通。01...【详细内容】
2020-07-25  Tags: 排序算法  点击:(62)  评论:(0)  加入收藏
1 插入排序算法定义插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好...【详细内容】
2020-06-30  Tags: 排序算法  点击:(55)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条