就让我
她不在这里,她无处追寻,可她在我心里 -- 挥之不去
PHP 堆与堆排序

 堆排序快速排序归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。

PHP 堆管理代码如下:

<?php 
class heep{
	static function add(&$arr,$one){
		$arr[] = $one;
		self::up($arr,count($arr) -1);
	}
	// 下沉
	static function del(&$arr){
		$arr[0] = array_pop($arr);
		self::down($arr,0,count($arr)-1);
	}
	static function swap(&$arr,$i,$p){
		$tmp = $arr[$i];
		$arr[$i] = $arr[$p];
		$arr[$p] = $tmp;
	}
	// 增加元素 上浮
	static function up(&$arr,$i){
		$p = floor(($i-1)/2);
		while( $p >= 0 && $i > 0 && $arr[$p] > $arr[$i] ){
			self::swap($arr,$i,$p);
			$i = $p;
			$p = floor(($i-1)/2);
		}
	}
	// 下沉 $i开始 $n结束
	static function down(&$arr,$i,$n){
		$l = 2*$i + 1;
		while( $l <= $n ){
			if( $l+1 <= $n && $arr[$l+1]<$arr[$l]) $l ++;
			if( $arr[$l] > $arr[$i] ) break;
			self::swap($arr,$i,$l);
			$i = $l;
			$l = 2*$i + 1;
		}
	}
	// 将数组变成堆
	static function make(&$arr){  
		$n = count( $arr )-1;
	    for ($i = $n / 2 - 1; $i >= 0; $i--)  
	        self::down($arr,$i,$n);
	}
	// 将堆进行排序
	static function sort(&$arr){  
		$n = count( $arr )-1;
	    for ( $i=$n; $i >= 0; $i--){
	    	self::swap($arr,0,$i);
	        self::down($arr,0,$i-1);
	    }
	}
}

$arr = [10,40,30];
$arr = array();

heep::add($arr,40);
heep::add($arr,10);
heep::add($arr,30);
heep::add($arr,15);
heep::add($arr,8);
heep::add($arr,50);
heep::add($arr,20);
heep::add($arr,3);

echo join(',',$arr),'<br>';

heep::del($arr);
heep::del($arr);
heep::del($arr);
echo join(',',$arr),'<br>';

heep::sort($arr);
echo join(',',$arr),'<br>';

$arr = [40,10,30];
heep::make($arr);
echo join(',',$arr),'<br>';
<< 上一篇 PHP 使用401鉴定登录 php static静态属性和静态方法的调用 下一篇 >>
文章标签
随意 | Created At 2014 By William Clinton | Contact Me: 1619488373@qq.com | 蜀ICP备14002619号 |