namespace iphpalgorithm;
class Sort
{
public static function bubble($arr)
{
$num=count($arr);
if($num<=1)
return $arr;
//些标识用于判断如果有一次没有经过交换。那么不需要再进行下一次循环
$flag=false;
for($i=0;$i<$num-1;$i++)
{
for($j=0;$j<$num-1-$i;$j++)
{
//交换元素
if($arr[$j]>$arr[$j+1])
{
$tmp=$arr[$j];
$arr[$j]=$arr[$j+1];
$arr[$j+1]=$tmp;
$flag=true;
}
}
if($flag==false)
break;
}
return $arr;
}
public static function select($arr)
{
$num=count($arr);
if($num<=1)
return $arr;
for($i=0;$i<$num-1;$i++)
{
$minValue=$arr[$i];
$minIndex=$i;
for($j=$i+1;$j<$num;$j++)
{
if($minValue>$arr[$j])
{
$minValue=$arr[$j];
$minIndex=$j;
}
}
//交换位置
if($i!=$j)
{
$tmp=$arr[$i];
$arr[$i]=$minValue;
$arr[$minIndex]=$tmp;
}
}
return $arr;
}
public static function insert($arr)
{
$num=count($arr);
if($num<=1)
return $arr;
for($i=1;$i<$num;$i++)
{
$insertValue=$arr[$i];
$insertIndex=$i-1;
while($insertIndex>=0 && $insertValue<$arr[$insertIndex])
{
$arr[$insertIndex+1]=$arr[$insertIndex];
$insertIndex--;
}
$arr[$insertIndex+1]=$insertValue;
}
return $arr;
}
public static function quick($arr)
{
$num=count($arr);
if($num<=1)
return $arr;
$middle=$arr[0];
$leftArr=array();
$rightArr=array();
for($i=1;$i<$num;$i++)
{
if($arr[$i]<=$middle)
$leftArr[]=$arr[$i];
else
$rightArr[]=$arr[$i];
}
$leftArr=self::quick($leftArr);
$rightArr=self::quick($rightArr);
return array_merge($leftArr,array($middle),$rightArr);
}
}
