当前位置:首页 > PHP教程 > php高级应用 > 列表

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

发布:smiling 来源: PHP粉丝网  添加日期:2021-11-14 20:58:30 浏览: 评论:0 

在本篇文章里小编给大家整理了关于PHP快速排序算法实现的原理及代码相关知识点,需要的朋友们跟着学习下。

算法原理

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

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

步骤:

从数组中选个基准值

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

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

代码实现

  1. function quickSort($arr
  2.  
  3.  
  4.  $len = count($arr); 
  5.  
  6.  if ($len <= 1) { 
  7.  
  8.   return $arr
  9.  
  10.  } 
  11.  
  12.  $v = $arr[0]; 
  13.  
  14.  $low = $up = array(); 
  15.  
  16.  for ($i = 1; $i < $len; ++$i) { 
  17.  
  18.   if ($arr[$i] > $v) { 
  19.  
  20.    $up[] = $arr[$i]; 
  21.  
  22.   } else { 
  23.  
  24.    $low[] = $arr[$i]; 
  25.  
  26.   } 
  27.  
  28.  } 
  29.  
  30.  $low = quickSort($low); 
  31.  
  32.  $up = quickSort($up); 
  33.  
  34.  return array_merge($lowarray($v), $up); 
  35.  

测试代码:

  1. $startTime = microtime(1); 
  2.  
  3. $arr = range(1, 10); 
  4.  
  5. shuffle($arr); 
  6.  
  7. echo "before sort: ", implode(', '$arr), "\n"
  8.  
  9. $sortArr = quickSort($arr); 
  10.  
  11. echo "after sort: ", implode(', '$sortArr), "\n"
  12.  
  13. echo "use time: ", microtime(1) - $startTime"s\n"

测试结果:

  1. before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8 
  2.  
  3. after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 
  4.  
  5. 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快速排序算法

分享到:

相关文章