冒泡排序(BubbleSort),是一种较简单的、稳定的排序算法。冒泡排序算法步骤:比较相邻的元素,如果第一个比第二个大,就交换他们两个的位置;对每对相邻的元素执行同样的操作,这样一趟下来,最后的元素就是最大的;除了已得出来的最大元素,把剩余的元素重复前面步骤,直到没有元素再需要比较为止,这样排序就完成了。下面学步园小编来讲解下PHP怎样实现冒泡排序、双向冒泡排序?
PHP怎样实现冒泡排序、双向冒泡排序
/**
*数据结构与算法(PHP实现)-冒泡排序(BubbleSort)。
*
*@author创想编程(TOPPHP.ORG)
*@copyrightCopyright(c)2013创想编程(TOPPHP.ORG)AllRightsReserved
*@licensehttp://www.opensource.org/licenses/mit-license.phpMITLICENSE
*@version1.0.0-Build20130608
*/
classBubbleSort{
/**
*冒泡排序。
*
*@varinteger
*/
constSORT_NORMAL=1;
/**
*双向冒泡排序。
*
*@varinteger
*/
constSORT_DUPLEX=2;
/**
*需要排序的数据数组。
*
*@vararray
*/
private$data;
/**
*数据数组的长度。
*
*@varinteger
*/
private$size;
/**
*数据数组是否已排序。
*
*@varboolean
*/
private$done;
/**
*构造方法-初始化数据。
*
*@paramarray$data需要排序的数据数组。
*/
publicfunction__construct(array$data){
$this->data=$data;
$this->size=count($this->data);
$this->done=FALSE;
}
/**
*交换数据数组中两个元素的位置。
*
*@paraminteger$x元素在数组中的索引。
*@paraminteger$y元素在数组中的索引。
*/
privatefunctionswap($x,$y){
$temp=$this->data[$x];
$this->data[$x]=$this->data[$y];
$this->data[$y]=$temp;
}
/**
*冒泡排序。
*/
privatefunctionsort(){
$this->done=TRUE;
for($i=1;$i<$this->size;++$i){
//记录交换数据的次数。
$swap=0;
for($j=$this->size-1;$j>$i-1;--$j){
if($this->data[$j]<$this->data[$j-1]){
$this->swap($j-1,$j);
++$swap;
}
}
//若交换数据的次数为0,说明数据数组已有序,不必再进行排序。
if(0===$swap){
break;
}
}
}
PHP怎样实现冒泡排序、双向冒泡排序
/**
*双向冒泡排序。
*/
privatefunctionduplexSort(){
$this->done=TRUE;
for($i=1;$i<=floor($this->size/2);++$i){
//记录交换数据的次数。
$swap=0;
for($j=$this->size-1,$k=$i-1;
$j>$i-1&&$k<$this->size-1;--$j,++$k){
if($this->data[$j]<$this->data[$j-1]){
$this->swap($j-1,$j);
++$swap;
}
if($this->data[$k]>$this->data[$k+1]){
$this->swap($k,$k+1);
++$swap;
}
}
//若交换数据的次数为0,说明数据数组已有序,不必再进行排序。
if(0===$swap){
break;
}
}
}
/**
*获取排序后的数据数组。
*
*@paraminteger$sort排序算法:SORT_NORMAL为冒泡排序;SORT_DUPLEX为双向冒泡排序。
*@returnarray返回排序后的数据数组。
*/
publicfunctiongetResult($sort=self::SORT_NORMAL){
//若已排序则无需再进行排序,直接返回排序好的数据数组。
if($this->done){
return$this->data;
}
switch($sort){
caseself::SORT_DUPLEX:
$this->duplexSort();
break;
caseself::SORT_NORMAL:
default:
$this->sort();
break;
}
return$this->data;
}
}
?>
示例代码1
2
3
4
$bubble=newBubbleSort(array(35,75,92,41,27,58));
echo'
',print_r($bubble->getResult(BubbleSort::SORT_DUPLEX),TRUE),'
';
?>
以上就是关于“PHP怎样实现冒泡排序、双向冒泡排序”的内容,希望对大家有用。更多资讯请关注学步园。学步园,您学习IT技术的优质平台!