php实现快速排序的三种方法

2024年4月16日发(作者：)

php实现快速排序的三种方法

php实现快速排序的三种方法

三种php快速排示例，第一种效率低但最简单最容易理解，第二个是算法导论上提

供的单向一次遍历找中值方法，第三种是双向遍历找中值经典快排算法。下面是店铺为大

家带来的php实现快速排序的三种方法，欢迎阅读。

方法一：该方法比较直观，但损失了大量的空间为代价，使用了效率较低的.merge

函数。在三种方法中效率最低。最坏情况下算法退化为(O(n*n))

代码如下:

function quick_sort($array) {

if(count($array) <= 1) return $array;

$key = $array[0];

$rightArray = array();

$leftArray = array();

for($i = 1; $i < count($array); $i++) {

if($array[$i] >= $key) {

$rightArray[] = $array[$i];

} else {

$leftArray[] = $array[$i];

}

}

$leftArray = quick_sort($leftArray);

$rightArray = quick_sort($rightArray);

return array_merge($leftArray, array($key), $rightArray);

}

方法二：该算法来自算法导论，叫作Nico Lomuto方法（感兴趣goole上有详细说

明）使用最经典的单方向一次遍历找到中值。

但这种算法在最坏情况下（例如值相同的数组，需要n-1次划分，每一次划分需要

O(n) 时间去掉一个元素）最坏情况下为O(n*n)

代码如下: