排序算法学习之路——快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

上面部分是引用网上的说法，我对这些定义总是记不太清楚。

我们下面直接看实现步骤

1. 从数列中挑出一个元素，称为 “基准”（这个基准的找出方式有很多，在这里我们就默认使用第一个元素作为基准）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 从第二步中得到的基准的中间位置将数组分成两部分，递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子序列排序。
4. 重复第二步，直到子序列的数值个数为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);

以上是通过递归的方式实现快速排序的。递归，使用起来非常方便，可以使我们整体上把握程序的架构。对于底层的细节，系统已经帮我们做了，其实递归的底层借助的就是栈的机制。 我们自己亦可以不用递归，直接借助栈的机制实现上述快速排序算法，可以查看 快速排序 非递归实现。这样将更有助于我们对算法的实现机制有更深的理解。

希望本篇对大家有所帮助。