美文网首页
【PHP】快速排序的「递归」和「非递归」方式

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

作者: 马蹄哒 | 来源:发表于2020-03-13 16:41 被阅读0次
    • 递归
    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;
    }
    

    相关文章

      网友评论

          本文标题:【PHP】快速排序的「递归」和「非递归」方式

          本文链接:https://www.haomeiwen.com/subject/wxtdshtx.html