<?php
namespace iphp\algorithm;
/**
* Created by PhpStorm.
* User: 123
* Date: 14-9-3
* Time: 下午3:53
*/
class Sort
{
/**
* 冒泡排序
* 算法，相邻２个元素比较，如果前大于后者，交换位置
* 第一次比较，将最大的元素排在了最后。
* 需要n-1次冒泡
* @param $arr
* @return mixed
*/
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;
}
/**
* 选择排序
* 第一次，取每1-n个元素之间的最小值，与第０个元素比较，并将最小的放在前面。
* @param $arr
* @return mixed
*/
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;
}
/**
* 插入排序
* 最开始将数组的第一个元素当作已经排序的数组。将后面的元素与已排好序的比较，将其插入到已排序中的适当位置。
* @param $arr
* @return mixed
*/
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;
}
/**
* 快速排序
* @param $arr
* @return array
*/
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);
}
}