PHP快速排序算法实现的原理及代码详解

yipeiwu_com5年前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命令注入攻击

详解php命令注入攻击

这次实验内容为了解php命令注入攻击的过程,掌握思路。 命令注入攻击 命令注入攻击(Command Injection),是指黑客通过利用HTML代码输入机制缺陷(例如缺乏有效验证限制的...

php精度计算的问题解析

PHP var_dump(intval(0.58 * 100)); 正确结果是 57,而不是 58 浮点运算惹的祸 其实这些结果都并非语言的 bug,但和语言的实现原理有关,...

php简单实现短网址(短链)还原的方法(测试可用)

php简单实现短网址(短链)还原的方法(测试可用)

本文实例讲述了php简单实现短网址还原的方法。分享给大家供大家参考,具体如下: 这里以【宜配屋www.yipeiwu.com】//www.jb51.net的短网址http://t.cn/...

PHP基础陷阱题(变量赋值)

复制代码 代码如下: <?php $a=3; $b=6; if($a=5||$b=7){ $a++; $b++; } var_dump($a, $b); 陷阱一 把$a=5、$b...

php实现的数组转xml案例分析

本文实例讲述了php实现的数组转xml。分享给大家供大家参考,具体如下: 0x00 需求 最近要做百度、360、神马搜索的网站sitemap,三家的格式都是xml,然而具体的细节还有有差...