排序算法口诀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次。
您可能感兴趣
- windowsserver2008部署php项目(win2008 r2 服务器环境配置FTP/ASP/ASP.Net/PHP)
- php 上传临时文件扩展名(浅析PHP 中move_uploaded_file 上传中文文件名失败)
- php静态类和动态类的区别(PHP Trait代码复用类与多继承实现方法详解)
- 自己在做项目过程中的php知识(PHP+Oracle本地开发环境搭建方法详解)
- php 支付系统(php 实现银联商务H5支付的示例代码)
- phpredis怎么设置队列(php使用lua+redis实现限流,计数器模式,令牌桶模式)
- php里的fpm是什么(phpfpm的作用和用法)
- php字符串教程学习(php学习笔记之字符串常见操作总结)
- pyclips入门(phpinfo的知识点总结)
- php-fpm配置文件在哪里(PHP-FPM 设置多pool及配置文件重写操作示例)
- thinkphp5数据库配置(Thinkphp5框架实现获取数据库数据到视图的方法)
- docker下怎么搭建一个php环境(Docker搭建php环境教程详解)
- php的字符串表达方法(php中字符串和整数比较的操作方法)
- phpsession方法(PHP SESSION机制的理解与实例)
- thinkphp5.0实例详解(ThinkPHP5&5.1框架关联模型分页操作示例)
- php如何设置命名空间(PHP进阶学习之命名空间基本用法分析)
- 阿里最新财报公布 三季度营收增长3 ,将增加150亿美元回购额度 在美股价小涨(阿里最新财报公布)
- 赵薇时胖时瘦 最近变美少女 原因在这里 躺着就变瘦(赵薇时胖时瘦最近变美)
- 学会这26种姿势,你就可以和兵哥哥切磋了(你就可以和兵哥哥切磋了)
- 吴彦祖陈冠希 恩怨 ,失去曾让他流泪的女友,终遇走过18年真爱(吴彦祖陈冠希恩怨)
- 痴情男神 吴彦祖 与妻子恋爱8年,结婚10年,家庭幸福美满(痴情男神吴彦祖)
- 成功破圈,小牛电动SQi强势开 跨(小牛电动SQi强势开)
热门推荐
- mysqlcount使用技巧(MySQL巧用sum、case和when优化统计查询)
- pythonssh登录服务器(对python 通过ssh访问数据库的实例详解)
- css怎么设置div边框(div+css实现带箭头的面包屑导航栏)
- laravel请求耗时(Laravel统计一段时间间隔的数据方法)
- 织梦dedecms开启付费授权(织梦dedeCMS二次开发文档手册 程序目录详解以及数据表结构字段)
- 阿里云ecs服务器挂了怎么办(阿里云ECS云服务器如何开放8080端口)
- python中的冒号怎么看(python 列表中[ ]中冒号‘:’的作用)
- vue移动端返回在指定位置(vue移动端判断手指在屏幕滑动方向)
- javascript和jquery的区别详解(JavaScript与JQuery框架基础入门教程)
- 什么是mongodb 固定集合
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9