作者:常沛威 | 来源:互联网 | 2018-03-20 19:50
php代码
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, "
\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;
}
}
}