10大经典排序算法之快速排序(PHP版)

发布时间:2020/11/20 作者:天马行空 阅读(159)

快速排序,是对冒泡排序的一种改进,它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


算法步骤
1、从数列中挑出一个基准元素;
2、比基准值小(大)的放到前面,比基准值大的放到后面;
3、把放到前面的子数组及放到后面的子数组分别递归,最后合并返回


动图演示

quickSort.gif


代码实现:

public function quickSort($arr)
{
    // 判断是否需要运行,因下面已拿出一个中间值,这里<=1
    if (count($arr) <= 1) {
        return $arr;
    }
    
    $middle = $arr[0]; // 中间值
    $left = array(); // 接收小于中间值
    $right = array(); // 接收大于中间值
                      
    // 循环比较
    for ($i = 1; $i < count($arr); $i ++) {
        if ($arr[$i] > $middle) {
            // 大于中间值
            $right[] = $arr[$i];
        } else {
            // 小于中间值
            $left[] = $arr[$i];
        }
    }
    
    // 递归排序划分好的2边
    $left = $this->kuaisu($left);
    $right = $this->kuaisu($right);
    
    // 合并排序后的数据,别忘了合并中间值
    return array_merge($left, array($middle), $right);
}



关键字php 算法