heapsort(PHP)

发表于:2007-07-01来源:作者:点击数: 标签:
练习堆排序的一个程序 ? //堆排序应用 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($
练习堆排序的一个程序

<?
//堆排序应用
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!!<br>@#;
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@#<font color=red>@#.$ok[$i].@#</font><br>@#;
        else
          echo$ok[$i].@#<br>@#;*/
      }
  }
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@#<font color=red>@#.$ok[$i].@#</font><br>@#;
        elseif($ok[$j]>$ok[$i])
          echo@#<font color=green>@#.$ok[$i].@#</font><br>@#;
        else
          echo$ok[$i].@#<br>@#;*/
      }
  }
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@#<font color=red>@#.$ok[$i].@#</font><br>@#;
        elseif($ok[$j]>$ok[$i])
          echo@#<font color=green>@#.$ok[$i].@#</font><br>@#;
        else
          echo$ok[$i].@#<br>@#;*/
      }
  }
else
  {
    echo@#参数输入错误!!<br>@#;
  }
//////
$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).@#秒时间@#;
//////
?>

原文转自:http://www.ltesting.net