用帝国软件做网站的心得,免费申请企业网站,个人注册域名可以做网站么,孝感新闻门户网站堆排序#xff1a;堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。1.堆堆实际上是一棵完全二叉树#xff0c;其任何一非叶节点满足性质#xff1a;Key[i]key[2i1]Key[i]key[2i2]或者Key[i]Key[2i1]keykey[2i2]即任何一非叶…堆排序堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。1.堆堆实际上是一棵完全二叉树其任何一非叶节点满足性质Key[i]key[2i1]Key[i]key[2i2]或者Key[i]Key[2i1]keykey[2i2]即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆满足Key[i]Key[2i1]keykey[2i2]称为大顶堆满足 Key[i]key[2i1]Key[i]key[2i2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的小顶堆的堆顶的关键字是所有关键字中最小的。2.堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆)1)将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无须区2)将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]R[n];3)由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。操作过程如下1)初始化堆将R[1..n]构造为堆2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换然后将新的无序区调整为新的堆。因此对于堆排序最重要的两个操作就是构造初始堆和调整堆其实构造初始堆事实上也是调整堆的过程只不过构造初始堆是对所有的非叶节点都进行调整。堆排序与快速排序归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前先讲解下什么是数据结构中的二叉堆。PHP 堆管理代码如下classheep{staticfunctionadd($arr,$one){$arr[] $one;self::up($arr,count($arr) -1);}// 下沉staticfunctiondel($arr){$arr[0] array_pop($arr);self::down($arr,0,count($arr)-1);}staticfunctionswap($arr,$i,$p){$tmp$arr[$i];$arr[$i] $arr[$p];$arr[$p] $tmp;}// 增加元素 上浮staticfunctionup($arr,$i){$pfloor(($i-1)/2);while($p 0 $i 0 $arr[$p] $arr[$i] ){self::swap($arr,$i,$p);$i$p;$pfloor(($i-1)/2);}}// 下沉 $i开始 $n结束staticfunctiondown($arr,$i,$n){$l 2*$i 1;while($l$n){if($l1 $n$arr[$l1]if($arr[$l] $arr[$i] )break;self::swap($arr,$i,$l);$i$l;$l 2*$i 1;}}// 将数组变成堆staticfunctionmake($arr){$ncount($arr)-1;for($i$n/ 2 – 1;$i 0;$i–)self::down($arr,$i,$n);}// 将堆进行排序staticfunctionsort($arr){$ncount($arr)-1;for($i$n;$i 0;$i–){self::swap($arr,0,$i);self::down($arr,0,$i-1);}}}$arr [10,40,30];$arrarray();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);echojoin(,,$arr),;heep::del($arr);heep::del($arr);heep::del($arr);echojoin(,,$arr),;//phpfensi.comheep::sort($arr);echojoin(,,$arr),;$arr [40,10,30];heep::make($arr);echojoin(,,$arr),;假设n为当前数组的key则,n的父节点为 n1 或者 n/2(整除);n的左子节点l n1 或 ln*2,n的右子节点r(n1)1 或 rl1,代码如下:$arrarray(1,8,7,2,3,4,6,5,9);数组$arr的原形态结构如下:1/8 7/ /2 3 4 6/5 9heapsort($arr);print_r($arr);排序后生成标准的小顶堆结构如下:1/2 3/ /4 5 6 7/8 9既数组:array(1,2,3,4,5,6,7,8,9):代码如下:functionheapsort($arr){//求最后一个元素位$lastcount($arr);//堆排序中通常忽略$arr[0]array_unshift($arr,0);//最后一个非叶子节点$i$last1;//整理成大顶堆,最大的数整到堆顶,并将最大数和堆尾交换,并在之后的计算中忽略数组后端的最大数(last),直到堆顶(last堆顶)while(true){adjustnode($i,$last,$arr);if($i1){//移动节点指针,遍历所有非叶子节点$i–;}else{//临界点last1,既所有排序完成if($last1)break;//当i为1时表示每一次的堆整理都将得到最大数(堆顶,$arr[1]),重复在根节点调整堆swap($arr[$last],$arr[1]);//在数组尾部按大小顺序保留最大数,定义临界点last,以免整理堆时重新打乱数组后面已排序好的元素$last–;}}//弹出第一个数组元素array_shift($arr);}//整理当前树节点($n),临界点$last之后为已排序好的元素functionadjustnode($n,$last,$arr){$l$n1;//$n的左孩子位if(!isset($arr[$l])||$l$last)return;$r$l1;//$n的右孩子位//如果右孩子比左孩子大,则让父节点的右孩子比if($r$last$arr[$r]$arr[$l])$l$r;//如果其中子节点$l比父节点$n大,则与父节点$n交换if($arr[$l]$arr[$n]){//子节点($l)的值与父节点($n)的值交换swap($arr[$l],$arr[$n]);//交换后父节点($n)的值($arr[$n])可能还小于原子节点($l)的子节点的值,所以还需对原子节点($l)的子节点进行调整,用递归实现adjustnode($l,$last,$arr);}}//交换两个值functionswap($a,$b){$a$a^$b;$b$a^$b;$a$a^$b;}
