排序算法口诀php(PHP快速排序算法实现的原理及代码详解)
类别:编程学习 浏览量:666
时间:2022-03-31 22:15:55 排序算法口诀php
PHP快速排序算法实现的原理及代码详解算法原理
下列动图来自五分钟学算法,演示了快速排序算法的原理和步骤。
步骤:
从数组中选个基准值
将数组中大于基准值的放同一边、小于基准值的放另一边,基准值位于中间位置
递归的对分列两边的数组再排序
代码实现
|
function quicksort( $arr ) { $len = count ( $arr ); if ( $len <= 1) { return $arr ; } $v = $arr [0]; $low = $up = array (); for ( $i = 1; $i < $len ; ++ $i ) { if ( $arr [ $i ] > $v ) { $up [] = $arr [ $i ]; } else { $low [] = $arr [ $i ]; } } $low = quicksort( $low ); $up = quicksort( $up ); return array_merge ( $low , array ( $v ), $up ); } |
测试代码:
|
$starttime = microtime(1); $arr = range(1, 10); shuffle( $arr ); echo "before sort: " , implode( ', ' , $arr ), "\n" ; $sortarr = quicksort( $arr ); echo "after sort: " , implode( ', ' , $sortarr ), "\n" ; echo "use time: " , microtime(1) - $starttime , "s\n" ; |
测试结果:
|
before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8 after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 use time: 0.0009009838104248s |
时间复杂度
快速排序的时间复杂度在最坏情况下是o(n2),平均的时间复杂度是o(n*lgn)。
这句话很好理解:假设被排序的数列中有n个数。遍历一次的时间复杂度是o(n),需要遍历多少次呢?至少lg(n+1)次,最多n次。
1) 为什么最少是lg(n+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(n+1)。因此,快速排序的遍历次数最少是lg(n+1)次。
2) 为什么最多是n次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是n。因此,快读排序的遍历次数最多是n次。
您可能感兴趣
- thinkphp怎么输出二维值(thinkphp 表名 大小写 窍门)
- php对接微信付款(PHP微信支付功能示例)
- phpstudy最佳配置(phpstudy如何开启openSSL?)
- phplaravel怎么优化(laravel执行php artisan migrate报错的解决方法)
- php读取远程的txt文件(php 根据URL下载远程图片、压缩包、pdf等文件到本地)
- php符串使用教程(php使用scandir函数扫描指定目录下所有文件示例)
- php处理app上传的图片(php用wangeditor3实现图片上传功能)
- php性能比较(php使用yield对性能提升的测试实例分析)
- php启用curl(php使用curl伪造浏览器访问操作示例)
- php如何发邮件(PHP示例演示发送邮件给某个邮箱)
- thinkphp标签详解(thinkphp整合系列之极验滑动验证码geetest功能)
- php执行超时怎么办(PHP错误提示It is not safe to rely on the system……的解决方法)
- php 经典模式(php设计模式之装饰模式应用案例详解)
- php在没有命名空间之前是怎么调(php命名空间设计思想、用法与缺点分析)
- php设计模式如何实现(php模式设计之观察者模式应用实例分析)
- dedecms兼容模式(DedeCMS 验证码不正确的解决方法php配置问题)
- 赵丽颖第一部当女主的戏,主角配角个个都是实力演员(赵丽颖第一部当女主的戏)
- 乾隆为何这么喜爱白塔原因是什么(乾隆为何这么喜爱白塔原因是什么)
- 逐渐消失的东北八大怪现象,进步的社会里我们遗失的是什么(逐渐消失的东北八大怪现象)
- 今日大雪,大雪养生这样做,一年都有好气色(大雪养生这样做)
- 粗盐是什么 粗盐的功效与作用(粗盐的功效与作用)
- 会 吃人 的客机 从天堂到地狱只需5分钟,图-104如何做到(会吃人的客机)
热门推荐
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9