php之快速排序

快速排序说明

• 取一个基数，比它大的放右边，比它小的放左边。
• 2.然后分别对取出的left 和 right 再做排序（递归）也是按照取一个计数，按照比它大的放右边，比它小的放左边。
• 3.合并left,basic right 的值，最后使整个序列有序。

无重复值快速排序

function quickSort($arr){
    $length = count($arr);
    if($length <=1){
        return $arr;
    }

    $basic  = $arr[0];
    $left   = [];
    $right  = [];

    for($i=0;$i < $length;$i++){
        if($arr[$i] < $basic){
            $left[] = $arr[$i];
        }

        if($arr[$i] > $basic){
            $right[] = $arr[$i];
        }
    }

## 针对Left 递归来说~~~每次递归都会执行一次相同的运--即取一个基数，比它大的放右边，比它小的放左边。最后剩下1个值就没必要比较了，然后依次return 返回合并的数组，直到返回给最外层为止。

    $left  = quickSort($left);
    $left[] = $basic;
    $right = quickSort($right);

    return array_merge($left,$right);
}

$arr = [23,38,22,45,23,67,31,15,41];
print_r(quickSort($arr));

有重复值的快速排序

function quickSort2($arr)
{
    $length = count($arr);
    if(count($arr) <= 1){
        return $arr;
    }
    $basic = $arr[0];
    /*
     在此处截取basixc元素 而不是在循环中判断的原因是: 原数组中如果有重复的值的话，循环中的判断会导致重复值
    只会出现一次。
      ###如下写法会导致重复值出现一次
        if($basic > $arr[$i]){
            $leftArr[] = $arr[$i];
        }

        if($basic < $arr[$i]){
            $rightArr[] = $arr[$i];
        }
    */

    array_splice($arr,0,1);

    $leftArr  = [];
    $rightArr = [];


    for($i=0;$i < count($arr);$i++){
        if($basic > $arr[$i]){
            $leftArr[] = $arr[$i];
        }else{
             $rightArr[] = $arr[$i];
        }
    }


    $leftArr = quickSort($leftArr);
    $leftArr[] = $basic;
    $rightArr = quickSort($rightArr);

    return array_merge($leftArr,$rightArr);
}

$arr = [22,38,22,45,23,67,31,15,41];
print_r(quickSort2($arr));

借鉴 http://harttle.land/2015/09/27/quick-sort.html