递归调用 - 关于php的快速排序，如何递归？-php教程-PHP中文网

递归调用 - 关于php的快速排序，如何递归？

php中文网

发布： 2016-06-06 20:12:16

原创

1186人浏览过

我想实现php下的递归，下面这段代码只能实现第一次排序，
但是不知道如何实现递归，了解了通过把两个左右数组merge一下，还是傻傻搞不明白。
请教各位，帮忙把代码优化下，或者贴下结果。谢谢~

 <?php

 $arr=[66,13,51,76,81,26,57,69,23];

 function swap(&$a,&$b){
    $tmp=$a;
    $a=$b;
    $b=$tmp;
    unset($tmp);
    return true;
 }
function quicksort($arr){
    
    $i=0;
    $j=count($arr)-1;
    $tmpb=$arr[0];// 基准元素 pivot

    while($arr[$i]!==$arr[$j]){
        //先从最右边找
        while ($arr[$j]>$tmpb){
            echo $arr[$j],"比",$tmpb,"大 go on ","\n";
            --$j;
            echo '$j',"减1,下标为",$j,"值为--";echo $arr[$j]."\n";
            echo '现在数组为',"\n";
            var_dump($arr);
        }
        // 如果这个值比pivot小了，那么就交换，然后从开始到左边找
        if($arr[$j]<$tmpb){
            echo $arr[$j],"比",$tmpb,"小了~ ";
            echo '交换',"\n";
            swap($arr[$j],$arr[$i]);
            ++$i;
            echo '现在数组为',"\n";
            var_dump($arr);
            echo '$i',"加1,下标为",$i,"值为--";echo $arr[$i]."\n";
            echo "在从左边开始";
            echo "\n";
        }
        // 然后从左边开始找
        while($arr[$i]<$tmpb){
            echo $arr[$i],'比',$tmpb,'小 go on ',"\n",'';
            ++$i;
            echo '$i',"加1,下标为",$i,"值为---";echo $arr[$i]."\n";
        }

        if($arr[$i]>$tmpb){
            echo $arr[$i],'比',$tmpb,'大了，交换';
            swap($arr[$i],$arr[$j]);
            --$j;
            echo '$j',"减1,下标为",$j,"值为--";echo $arr[$j]."\n";
            echo '现在数组为',"\n";
            var_dump($arr);
            echo "在从右边边开始";
            echo '再走一层最外层while',"\n";
            }
}

    return $arr;
}
$result=quicksort($arr);
echo "========================","最终结果为\n";
var_dump($result);

登录后复制

执行的结果我贴一下：
========================最终结果为
array (
0 => 23,
1 => 13,
2 => 51,
3 => 57,
4 => 26,
5 => 66,
6 => 81,
7 => 69,
8 => 76,
)他只是按找66分成了左右两部分，结合我上面的思路,怎么能递归呢?

回复内容：

 <?php

 $arr=[66,13,51,76,81,26,57,69,23];

 function swap(&$a,&$b){
    $tmp=$a;
    $a=$b;
    $b=$tmp;
    unset($tmp);
    return true;
 }
function quicksort($arr){
    
    $i=0;
    $j=count($arr)-1;
    $tmpb=$arr[0];// 基准元素 pivot

    while($arr[$i]!==$arr[$j]){
        //先从最右边找
        while ($arr[$j]>$tmpb){
            echo $arr[$j],"比",$tmpb,"大 go on ","\n";
            --$j;
            echo '$j',"减1,下标为",$j,"值为--";echo $arr[$j]."\n";
            echo '现在数组为',"\n";
            var_dump($arr);
        }
        // 如果这个值比pivot小了，那么就交换，然后从开始到左边找
        if($arr[$j]<$tmpb){
            echo $arr[$j],"比",$tmpb,"小了~ ";
            echo '交换',"\n";
            swap($arr[$j],$arr[$i]);
            ++$i;
            echo '现在数组为',"\n";
            var_dump($arr);
            echo '$i',"加1,下标为",$i,"值为--";echo $arr[$i]."\n";
            echo "在从左边开始";
            echo "\n";
        }
        // 然后从左边开始找
        while($arr[$i]<$tmpb){
            echo $arr[$i],'比',$tmpb,'小 go on ',"\n",'';
            ++$i;
            echo '$i',"加1,下标为",$i,"值为---";echo $arr[$i]."\n";
        }

        if($arr[$i]>$tmpb){
            echo $arr[$i],'比',$tmpb,'大了，交换';
            swap($arr[$i],$arr[$j]);
            --$j;
            echo '$j',"减1,下标为",$j,"值为--";echo $arr[$j]."\n";
            echo '现在数组为',"\n";
            var_dump($arr);
            echo "在从右边边开始";
            echo '再走一层最外层while',"\n";
            }
}

    return $arr;
}
$result=quicksort($arr);
echo "========================","最终结果为\n";
var_dump($result);

登录后复制

立即学习“PHP免费学习笔记（深入）”；

public static function quickSort( $numArr )
{
    $minArr = [];
    $maxArr = [];
    $randKey = array_rand( $numArr );
    $baseNum = $numArr[$randKey];
    unset( $numArr[$randKey] );
    foreach ( $numArr as $num )
    {
        if ( $num >= $baseNum )
            $maxArr[] = $num;
        else
            $minArr[] = $num;
    }
    if ( count( $maxArr ) > 1 )
        $maxArr = self::quickSort( $maxArr );
    if ( count( $minArr ) > 1 )
        $minArr = self::quickSort( $minArr );
    return array_merge( $minArr, [$baseNum], $maxArr );
}`

登录后复制

我是这么做的