【PHP】快速排序的「递归」和「非递归」方式

• 递归

function quickSort1($arr)
{
    $len = count($arr);
    if ($len<2){
        return $arr;
    }

    $min = $max = $base = [];
    $base_item = $arr[0];
    for ($i=0; $i<$len; $i++){
        if ($arr[$i]<$base_item){
            $min[] = $arr[$i];
        }elseif($arr[$i]>$base_item){
            $max[] = $arr[$i];
        }else{
            $base[] = $arr[$i];
        }
    }
    $min = $this->quickSort($min);
    $max = $this->quickSort($max);
    return array_merge($max,$base,$min);
}

• 非递归

function quickSort($arr)
{
    $borderStack[] = [0, count($arr) - 1]; //数组边界
    while (!empty($borderStack))
    {
        $border = array_pop($borderStack);
        $left = $border[0];
        $right = $border[1];
        $pivot = $arr[$left]; // 分界值
        while ($left < $right)
        {
            while ($left<$right && $arr[$right] >= $pivot) $right--;
            $arr[$left] = $arr[$right];
            while ($left<$right && $arr[$left] < $pivot) $left++;
            $arr[$right] = $arr[$left];
        }
        //$left 等于 $right :
        $arr[$left] = $pivot;
        if ($border[0] < $left - 1) $borderStack[] = [$border[0],$left-1];
        if ($border[1] > $left + 1) $borderStack[] = [$left+1, $border[1]];
    }
    return $arr;
}