PHP快速排序算法实现的原理及代码介绍

本篇文章给大家带来的内容是关于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, "sn";

测试结果:

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中文网其它相关文章!

PHP快速排序算法实现的原理及代码介绍

  • 相关标签:php 算法 排序 快速排序
  • 本文转载于:segmentfault,如有侵犯,请联系删除
    • 上一篇:php哈希表及数组的介绍(附代码)
    • 下一篇:PHP实现二元一次方程式的求解

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注