練習(xí)堆排序的一個程序

//堆排序應(yīng)用
class heapsort
? {
??? var $a;
??? function setarray($a)//取得數(shù)組
????? {
??????? $this->a=$a;
????? }
??? function runvalue($b,$c)//$a 代表數(shù)組，$b代表排序堆,$c代表結(jié)束點,
????? {
??????? while($b????????? {
??????????? $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--)//先將數(shù)組建立成堆
????????? {
??????????? $this->runvalue($i,($all-1));
????????? }
??????? for($i=1;$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)//取得數(shù)組
????? {
??????? $this->a=$a;
????? }
??? function runvalue($i)
????? {
??????? $max=$this->a[$i];
??????? $id=$i;
??????? for($j=($i+1);$ja);$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;$ia)-1);$i++)
????????? $this->runvalue($i);
??????? return $this->a;
????? }
? }
//////
$s=microtime();
$st=explode(' ',$s);
$st1=$st[0];
$st2=$st[1];
//////
$v=10000;//排序數(shù)組長度
$brr[0]=0;
for($i=1;$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????? {
??????? $j=((($i+1)>($v-1))?($v-1):($i+1));
? /*
?if($ok[$j]????????? echo''.$ok[$i].'
';
??????? else
????????? echo$ok[$i].'
';*/
????? }
? }
elseif($check==2)
? {
??? $arr=new sortarr;
??? $arr->setarray($brr);
??? $ok=$arr->getarray();
??? for($i=1;$i????? {
??????? $j=((($i+1)>($v-1))?($v-1):($i+1));/*
??????? if($ok[$j]????????? 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????? {
??????? $j=((($i+1)>($v-1))?($v-1):($i+1));/*
??????? if($ok[$j]????????? echo''.$ok[$i].'
';
??????? elseif($ok[$j]>$ok[$i])
????????? echo''.$ok[$i].'
';
??????? else
????????? echo$ok[$i].'
';*/
????? }
? }
else
? {
??? echo'參數(shù)輸入錯誤!!
';
? }
//////
$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='常規(guī)排序';
elseif($check==3)
? $word='普通排序';
else
? $word='無排序';
echo$word.'對具有'.$v.'個元素的數(shù)組排序,消耗了'.($ss2+$ss1).'秒時間';
//////
?>