PHP算法之快排算法

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


代码实现:

function qsort(array $arr)
{
    //判断是否为数组或者为空就返回一个数组
    if(!is_array($arr) || empty($arr)){
        return array();
    }
    $len=count($arr);
    //判断如果数组的长度等于或者小于1,那就没有必要进行排序直接返回
    if($len<=1){
        return $arr;
    }
    //定义一个中间值 一般以第一个数值为例
    $key[0]=$arr[0];
    //定义左边集合
    $left=array();
    //定义右边集合
    $right=array();
    //判断 如果比较这个数小于这个中间值,那就放左边,大于的话就放右边
    for ($i=1;$i<$len;$i++){
        if($arr[$i]<$key[0]){
            $left[]=$arr[$i];
        }else{
            $right[]=$arr[$i];
        }
    }
    //判断了之后得到两个数组 但是还是得进行比较,并且对原数组进行替换
    $left=qsort($left);
    $right=qsort($right);
    //然后进行返回数组
    return array_merge($left,$key,$right);

}
print_r(qsort($arr));


打赏

本文 暂无 评论

回复给

Top