heapsort(PHP)

练习堆排序的一个程序

<?
//堆排序应用
class heapsort
{
 var $a;
 function setarray($a)//取得数组
 {
 $this->a=$a;
 }
 function runvalue($b,$c)//$a 代表数组，$b代表排序堆,$c代表结束点,
 {
 while($b<$c)
 {
 $h1=2*$b;
 $h2=(2*$b+1);
 if($h1>$c)
 break;
 elseif($h1==$c)
 {
 if($this->a[$b]>$this->a[$h1])
 {
 $t=$this->a[$b];
 $this->a[$b]=$this->a[$h1];
 $this->a[$h1]=$t;
 $la=1;
 }
 else
 $la=1;
 }
 elseif(($this->a[$b]>$this->a[$h1])||($this->a[$b]>$this->a[$h2]))
 {
 if($this->a[$h1]>=$this->a[$h2])
 {
 $t=$this->a[$h2];
 $this->a[$h2]=$this->a[$b];
 $this->a[$b]=$t;
 $b=$h2;
 }
 else
 {
 $t=$this->a[$h1];
 $this->a[$h1]=$this->a[$b];
 $this->a[$b]=$t;
 $b=$h1;
 }
 }
 else
 $la=1;
 if($la==1)
 break;
 }
 }
 function getarray()
 {
 $all=count($this->a);
 $b=Floor(($all-1)/2);
 for($i=$b;$i>=1;$i--)//先将数组建立成堆
 {
 $this->runvalue($i,($all-1));
 }
 for($i=1;$i<$all;$i++)
 {
 $a1=($all-$i);
 if($i==1)
 {
 $t=$this->a[1];
 $this->a[1]=$this->a[$a1];
 $this->a[$a1]=$t;
 }
 else
 {
 $end=($all-$i);
 $this->runvalue(1,$end);
 $t=$this->a[1];
 $this->a[1]=$this->a[$end];
 $this->a[$end]=$t;
 }
 }
 return $this->a;
 }
}
//////
class sortarr
{
 var $a;
 function setarray($a)//取得数组
 {
 $this->a=$a;
 }
 function runvalue($i)
 {
 $max=$this->a[$i];
 $id=$i;
 for($j=($i+1);$j<count($this->a);$j++)
 {
 if($this->a[$j]>$max)
 {
 $max=$this->a[$j];
 $id=$j;
 }
 }
 if($id!=$i)
 {
 $t=$this->a[$id];
 $this->a[$id]=$this->a[$i];
 $this->a[$i]=$t;
 }
 }
 function getarray()
 {
 for($i=1;$i<(count($this->a)-1);$i++)
 $this->runvalue($i);
 return $this->a;
 }
}
//////
$s=microtime();
$st=explode(@# @#,$s);
$st1=$st[0];
$st2=$st[1];
//////
$v=10000;//排序数组长度
$brr[0]=0;
for($i=1;$i<$v;$i++)
{
 $brr[$i]=rand();
}
$check=2;//1 stand for heapsort 2 stand for another sort
echo@#after sort!! @#;
if($check==1)
{
 $arr=new heapsort;
 $arr->setarray($brr);
 $ok=$arr->getarray();
 for($i=1;$i<$v;$i++)
 {
 $j=((($i+1)>($v-1))?($v-1):($i+1));
/*
if($ok[$j]<$ok[$i])
 echo@#@#.$ok[$i].@# @#;
 else
 echo$ok[$i].@# @#;*/
 }
}
elseif($check==2)
{
 $arr=new sortarr;
 $arr->setarray($brr);
 $ok=$arr->getarray();
 for($i=1;$i<$v;$i++)
 {
 $j=((($i+1)>($v-1))?($v-1):($i+1));/*
 if($ok[$j]<$ok[$i])
 echo@#@#.$ok[$i].@# @#;
 elseif($ok[$j]>$ok[$i])
 echo@#@#.$ok[$i].@# @#;
 else
 echo$ok[$i].@# @#;*/
 }
}
elseif($check==3)
{
 sort($brr);
 $ok=$brr;
 for($i=1;$i<$v;$i++)
 {
 $j=((($i+1)>($v-1))?($v-1):($i+1));/*
 if($ok[$j]<$ok[$i])
 echo@#@#.$ok[$i].@# @#;
 elseif($ok[$j]>$ok[$i])
 echo@#@#.$ok[$i].@# @#;
 else
 echo$ok[$i].@# @#;*/
 }
}
else
{
 echo@#参数输入错误!! @#;
}
//////
$s=microtime();
$st=explode(@# @#,$s);
$sta=$st[0];
$stb=$st[1];
$ss1=$sta-$st1;
$ss2=$stb-$st2;
if($check==1)
$word=@#堆排序@#;
elseif($check==2)
$word=@#常规排序@#;
elseif($check==3)
$word=@#普通排序@#;
else
$word=@#无排序@#;
echo$word.@#对具有@#.$v.@#个元素的数组排序,消耗了@#.($ss2+$ss1).@#秒时间@#;
//////
?>

下一篇：一个双向加密解密法(php)

↓相关文章：