迹忆博客
当前位置: 主页 > 学无止境 > 算法 > 文章

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

发布时间: 2016-04-08 作者: 迹忆 浏览次数:

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 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);

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

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

赞助
迹忆博客

除非注明转载,本站文章均为原创,欢迎转载,转载请以链接形式注明出处

本文地址: