PHP快速排序实现原理及详细代码说明

算法原理

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

步骤：

从数组中选择一个参考值

将大于参考值的放在同一侧，小于参考值的放在阵列的另一侧，参考值放在中间位置

递归地对列两边的数组重新排序

代码实现

函数quick sort($ 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=quick sort($ low)；$ up=quick sort($ up)；return array_merge($low，array($v)，$ up)；}测试代码：

$ start time=micro time(1)；$arr=范围(1，10)；shuffle($ arr)；echo 'before sort: '，内爆('，'，$arr)，' \ n '；$ sort RR=quick sort($ arr)；echo 'after sort: '，内爆('，'，$ sortArr)，' \ n '；echo 'use time: '，microtime(1) - $startTime，' s \ n '；测试结果：

排序3360之前的1，7，10，9，6，3，2，5，4，8排序3360之后的1，2，3，4，5，6，7，8，9，10的时间复杂度使用时间s。56860 . 66666666666

最坏情况下，快速排序的时间复杂度为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次。