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

站长资源 2024/11/28 佚名

2 0 1

算法原理

下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。

步骤:

从数组中选个基准值

将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置

递归的对分列两边的数组再排序

代码实现

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,快速排序

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

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

暂无评论...

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

2024年11月28日

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

从ThinkPHP3.2.3过渡到ThinkPHP5.0学习笔记图文详解

Laravel5.7框架安装与使用学习笔记图文详解

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

P70系列延期，华为新旗舰将在下月发布

更新日志

友情链接