快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
上面部分是引用网上的说法，我对这些定义总是记不太清楚。
我们下面直接看实现步骤
1 . 从数列中挑出一个元素，称为 “基准”（这个基准的找出方式有很多，在这里我们就默认使用第一个元素作为基准）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 从第二步中得到的基准的中间位置将数组分成两部分，递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子序列排序。
- 重复第二步，直到子序列的数值个数为1
其中一次排序的过程可以参考下图
快速排序过程
上面我们了解了一趟找基准位置的过程，下面我们做的只需要通过递归的方式按照基准的位置分割数组，依次对子数组进行上述过程。
下面我们看实现过程
function FindPv(&$arr,$s,$e){
$p = $s; //基准起始位置
$v = $arr[$p]; //将数组的第一个值作为基准值
while($s<$e){
while($arr[$e]>$v&&$e>$p){
$e--;
}
$arr[$p] = $arr[$e];
$p = $e;
while($arr[$s]<$v&&$s<$p){
$s++;
}
$arr[$p] = $arr[$s];
$p = $s;
}
$arr[$p] = $v;
return $p;
}
function PvSort(&$arr,$s,$e){
if($s>=$e) return ;
$nextP = FindPv($arr,$s,$e); //找到下一个基准所在位置
PvSort($arr,$s,$nextP-1);
PvSort($arr,$nextP+1,$e);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
PvSort($arr);
print_r($arr);
以上是通过递归的方式实现快速排序的。递归，使用起来非常方便，可以使我们整体上把握程序的架构。对于底层的细节，系统已经帮我们做了，其实递归的底层借助的就是栈的机制。 我们自己亦可以不用递归，直接借助栈的机制实现上述快速排序算法，可以查看 快速排序 非递归实现。这样将更有助于我们对算法的实现机制有更深的理解。
希望本篇对大家有所帮助。
