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

算法原理

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

步骤:

从数组中选个基准值

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

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

代码实现

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

测试代码:

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

分享到：