PHP快速排序算法实现的原理及代码详解
2019/6/30 16:12:41
本文主要是介绍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次。
这篇关于PHP快速排序算法实现的原理及代码详解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30百度空间安装易优,如何去除URL中的index.php-icode9专业技术文章分享
- 2024-06-30宝塔Linux服务器隐藏index.php-icode9专业技术文章分享
- 2024-03-29env: php: no such file or directory
- 2024-03-01php foreach break
- 2024-02-26Exception参数 php-icode9专业技术文章分享
- 2023-12-30PHP文件批量上传-icode9专业技术文章分享
- 2023-12-30thinkphp6 withJoin-icode9专业技术文章分享
- 2023-12-27MagicArray:像php一样,让Go业务代码不再卷!
- 2023-11-18centos7编译安装PHP教程。
- 2023-11-18centos7编译安装phpMyAdmin教程。