最近在看《程序设计方法》（HTDP，讲解编程思想的经典），看到介绍快速排序的例子，实现思想实在是简练，基本上看完一遍再也不会忘记的感觉。
实现思想：
1.把要排序的内容分成两部分，第一部分是小于第一个元素的，第二部分是大于等于第一个元素的.
2.对分出来的两部分表分别采用1的方法排序。
3.把这些数据连接起来
实现代码（php实现）：
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
42
43
44
<?php
function qsort($arr)
{
if (count($arr) <= 1)
return $arr;
$first = array_shift($arr);
return array_merge(
qsort(smallItems($first, $arr)),
array($first),
qsort(bigItems($first, $arr)));
}
//找出$arr中所有小于$item的元素
function smallItems($item, $arr)
{
return array_filter($arr, function($v) use ($item){return $v > $item;});
}
//找出$arr中所有大于$item的元素
function bigItems($item, $arr)
{
return array_filter($arr, function($v) use ($item){return $v <= $item;});
}
//测试部分
function testQsort()
{
assert('qsort(array()) === array()');
assert('qsort(array(1)) === array(1)');
for ($i=0;$i<100;$i++) {
$arr = randomArr(rand(0,1000));
$mySortArr = qsort($arr);
sort($arr);
assert('$mySortArr === $arr');
}
}
//随机生成一个长度为$count的数组，里面的数值随机
function randomArr($count)
{
$arr = array();
for($i = 0; $i < $count; $i++) {
$arr[] = rand(-1000, 1000);
}
return $arr;
}
?>
算法的思想简单易懂，代码只要根据步骤翻译就好了。