php堆排序?qū)崿F(xiàn)原理與應(yīng)用方法_

1、php堆排序?qū)崿F(xiàn)原理與應(yīng)用方法_ 這篇文章主要介紹了php堆排序?qū)崿F(xiàn)原理與應(yīng)用方法,較為具體的分析了堆排序的原理及用法技巧,具有肯定參考借鑒價(jià)值,需要的伴侶可以參考下 本文實(shí)例講解并描述了php堆排序?qū)崿F(xiàn)原理與應(yīng)用方法。分享給大家供大家參考。具體分析如下： 這里以php作為描述語言較具體講解堆排序原理,因保證程序可讀性,故不做優(yōu)化,php程序中關(guān)于堆的一些概念如下: 假設(shè)n為當(dāng)前數(shù)組的key則,n的父節(jié)點(diǎn)為 n1 或者 n/2(整除);n的左子節(jié)點(diǎn)l= n1 或 l=n*2,n的右子節(jié)點(diǎn)r=(n1)+1 或 r=l+1 $arr=array(1,8,7,2,3,4,6,5,9); 數(shù)組$arr

2、的原形態(tài)結(jié)構(gòu)如下: 1 / 8 7 / / 2 3 4 6 / 5 9 heapsort($arr);print_r($arr); 排序后生成標(biāo)準(zhǔn)的小頂堆結(jié)構(gòu)如下: 1 / 2 3 / / 4 5 6 7 / 8 9 既數(shù)組:array(1,2,3,4,5,6,7,8,9): 代碼如下: function heapsort($arr) /求最終一個(gè)元素位 $last=count($arr); /堆排序中通常忽視$arr0 array_unshift($arr,0); /最終一個(gè)非葉子節(jié)點(diǎn) $i=$last1; /整理成大頂堆,最大的數(shù)整到堆頂,并將最大數(shù)和堆尾交換,并在之后的計(jì)算中忽視數(shù)組后端

3、的最大數(shù)(last),直到堆頂(last=堆頂) while(true) adjustnode($i,$last,$arr); if($i1) /移動(dòng)節(jié)點(diǎn)指針,遍歷全部非葉子節(jié)點(diǎn) $i-; else /臨界點(diǎn)last=1,既全部排序完成 if($last=1)break; /當(dāng)i為1時(shí)表示每一次的堆整理都將得到最大數(shù)(堆頂,$arr1),重復(fù)在根節(jié)點(diǎn)調(diào)整堆 swap($arr$last,$arr1); /在數(shù)組尾部按大小挨次保留最大數(shù),定義臨界點(diǎn)last,以免整理堆時(shí)重新打亂數(shù)組后面已排序好的元素 $last-; /彈出第一個(gè)數(shù)組元素 array_shift($arr); /整理當(dāng)前樹節(jié)點(diǎn)($

4、n),臨界點(diǎn)$last之后為已排序好的元素 function adjustnode($n,$last,$arr) $l=$n1; /$n的左孩子位 if(!isset($arr$l)|$l$last) return ; $r=$l+1; /$n的右孩子位 /假如右孩子比左孩子大,則讓父節(jié)點(diǎn)的右孩子比 if($r=$last$arr$r$arr$l) $l=$r; /假如其中子節(jié)點(diǎn)$l比父節(jié)點(diǎn)$n大,則與父節(jié)點(diǎn)$n交換 if($arr$l$arr$n) /子節(jié)點(diǎn)($l)的值與父節(jié)點(diǎn)($n)的值交換 swap($arr$l,$arr$n); /交換后父節(jié)點(diǎn)($n)的值($arr$n)可能還小于原子節(jié)點(diǎn)($l)的子節(jié)點(diǎn)的值,所以還需對原子節(jié)點(diǎn)($l)的子節(jié)點(diǎn)進(jìn)行調(diào)整,用遞歸實(shí)現(xiàn) adjustnode($l,$last,$arr); /交換兩個(gè)值 function swap($a,$b)