PHP快速排序算法实现的原理及代码介绍
内容导读
收集整理的这篇技术教程文章主要介绍了PHP快速排序算法实现的原理及代码介绍，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1611字，纯文字阅读大概需要3分钟。
内容图文
本篇文章给大家带来的内容是关于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, "sn";测试结果:
before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10use 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视频教程】
以上就是PHP快速排序算法实现的原理及代码介绍的详细内容，更多请关注Gxl网其它相关文章！
内容总结
以上是为您收集整理的PHP快速排序算法实现的原理及代码介绍全部内容，希望文章能够帮你解决PHP快速排序算法实现的原理及代码介绍所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
