算法原理
下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。
步骤:
从数组中选个基准值
将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置
递归的对分列两边的数组再排序
代码实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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);
}
|
测试代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
$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";
|
测试结果:
|
1
2
3
4
5
|
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次。