PHP快速排序算法实现的原理是什么

发布时间:2020-10-15 17:24:38 作者:小新
来源:亿速云 阅读:150

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次。

感谢各位的阅读!看完上述内容,你们对PHP快速排序算法实现的原理是什么大概了解了吗?希望文章内容对大家有所帮助。如果想了解更多相关文章内容,欢迎关注亿速云行业资讯频道。

推荐阅读:
  1. php中session的原理是什么
  2. PHP的工作原理是什么

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

php

上一篇:php实现共享内存进程通信函数之shm的方法

下一篇:Java基于Redis如何实现分布式锁

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》