PHP快速排序算法实现的原理及代码详解
发布:smiling 来源: PHP粉丝网 添加日期:2021-11-14 20:58:30 浏览: 评论:0
在本篇文章里小编给大家整理了关于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次。
Tags: PHP快速排序算法
相关文章
- ·PHP快速排序算法实例分析(2021-10-10)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)