数据结构与算法(php版)排序之快速排序

yang-pig| 阅读:449 发表时间:2018-07-29 20:39:00 算法

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

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

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

我们下面直接看实现步骤

1 、从数列中挑出一个元素,称为 “基准”(这个基准的找出方式有很多,在这里我们就默认使用第一个元素作为基准)

2、 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3、从第二步中得到的基准的中间位置将数组分成两部分,递归地(recursive)把小于基准值元素的子序列和大于基准值元素的子序列排序。

4、重复第二步,直到子序列的数值个数为1

Sorting_quicksort_anim.gif

(图解)

其中一次排序过程过程可以参考下图

1-16040QI640511.png

上面我们了解了一趟找基准位置的过程,下面我们做的只需要通过递归的方式按照基准的位置分割数组,依次对子数组上述过程。

下面我们看实现过程:


<?php
/**
 * 快速查询
 * -------------------------------------------------------------
 * 从数列中挑出一个元素,称为 “基准”(这个基准的找出方式有很多,在这里我们就默认使用第一个元素作为基准)
 * 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
 * 从第二步中得到的基准的中间位置将数组分成两部分,递归地(recursive)把小于基准值元素的子序列和大于基准值元素的子序列排序。
 * 重复第二步,直到子序列的数值个数为1
 * -------------------------------------------------------------
 * 重复第二步操作直至找出目标数字
 */

/**
 * @param $arr
 * @param $s
 * @param $e
 * @return mixed
 */
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,0,11);
var_dump($arr);