PHP快速排序算法（非遞歸）實現

quicksort.php ~ 1KB         

<?php

$i = 100;
while($i > 0){
    if($i > 30){
        $test[] = mt_rand($i - 30, $i--);
    }else{
        $test[] = mt_rand(1, $i--);
    }
}
//shuffle($test);
echo count($test), "\n";

//sort($test);
echo implode(", ", $test), "\n\n";
$t1 = microtime(true);

quicksort($test);
echo implode(", ", $test), "\n\n";
echo microtime(true) - $t1, "<br>\n";



function quicksort(array &$sort){
    $end = count($sort);
    if(--$end < 1){
        return;
    }

    $beg = 0;
    $stack = array();

    while(true){
        $i = $beg;
        $l = $end;
        $o = $sort[
            $x = mt_rand($i, $l)
        ];

        while($i < $l){
            // 左邊大于的
            if($sort[$i] > $o){
                while($i < $l){
                    // 右邊小于等于的
                    if($sort[$l] <= $o){
                        $tmp = $sort[$i];
                        $sort[$i] = $sort[$l];
                        $sort[$l] = $tmp;
                        $i++; $l--;
                        continue 2;
                    }
                    $l--;
                }
                goto re;
            }
            $i++;
        }
        if($sort[$i] < $o){
            $sort[$x] = $sort[$i];
            $sort[$i] = $o;
        }
//      echo $i, ", ", $l, "; ", $beg, ", ", $end, "\n";

    re:
        // 保存右邊
        if($i < $end){
            $stack[] = $i;
            $stack[] = $end;
        }
        if(--$i > $beg){
            $end = $i; // 繼續左邊
        }elseif($stack){
            // 返回繼續右邊
            $end = array_pop($stack);
            $beg = array_pop($stack);
        }else{
            break;
        }
    }
}