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;
}
网友评论