PHP排序算法之堆排序HeapSort的示例分析-創(chuàng)新互聯(lián)

小編給大家分享一下PHP排序算法之堆排序Heap Sort的示例分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

創(chuàng)新互聯(lián)公司專注于路北企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站設(shè)計(jì),電子商務(wù)商城網(wǎng)站建設(shè)。路北網(wǎng)站建設(shè)公司,為路北等地區(qū)提供建站服務(wù)。全流程按需定制制作，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

算法引進(jìn)：

在這里我直接引用《大話數(shù)據(jù)結(jié)構(gòu)》里面的開(kāi)頭：

在前面講到 簡(jiǎn)單選擇排序 ，它在待排序的 n 個(gè)記錄中選擇一個(gè)最小的記錄需要比較 n - 1 次，本來(lái)這也可以理解，查找第一個(gè)數(shù)據(jù)需要比較這么多次是正常的，否則如何知道他是最小的記錄。

可惜的是，這樣的操作并沒(méi)有把每一趟的比較結(jié)果保存下來(lái)，在后一趟的比較重，有許多比較在前一趟已經(jīng)做過(guò)了，但由于前一趟排序時(shí)未保存這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作，因而記錄的比較次數(shù)較多。

如果可以做到每次在選擇到最小記錄的同時(shí)，并根據(jù)比較結(jié)果對(duì)其他記錄做出相應(yīng)的調(diào)整，那樣排序的總體效率就會(huì)非常高了。而堆排序，就是對(duì)簡(jiǎn)單選擇排序進(jìn)行的一種改進(jìn)，這種改進(jìn)的效果是非常明顯的。

基本思想：

在介紹堆排序之前，我們先來(lái)介紹一下堆：

《大話數(shù)據(jù)結(jié)構(gòu)》里的定義：堆 是具有下列性質(zhì)的完全二叉樹(shù)：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值，成為大頂堆（大根堆）；或者每個(gè)節(jié)點(diǎn)的值都小于或等于其左右節(jié)點(diǎn)的值，成為小頂堆（小根堆）。

當(dāng)時(shí)我在看到這里的時(shí)候也對(duì)有“堆是否是完全二叉樹(shù)”有過(guò)疑問(wèn)，網(wǎng)上也有說(shuō)不是完全二叉樹(shù)的，但是無(wú)論堆是不是完全二叉樹(shù)，尚且保留意見(jiàn)。我們只要知道，在這里我們采用完全二叉樹(shù)形式的大根堆（小跟堆），主要是為了方便存儲(chǔ)和計(jì)算（后面我們會(huì)看到帶來(lái)的便利）。

堆排序算法：

堆排序就是利用堆（假設(shè)利用大根堆）進(jìn)行排序的方法，它的基本思想是：將待排序的序列構(gòu)造成一個(gè)大根堆。此時(shí)，整個(gè)序列的較大值就是堆頂?shù)母?jié)點(diǎn)。將它移走（其實(shí)就是將其與堆數(shù)組的末尾元素交換，此時(shí)末尾元素就是較大值），然后將剩余的 n - 1 個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到 n 個(gè)元素中的次小的值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了。

大根堆排序算法的基本操作：

①建堆，建堆是不斷調(diào)整堆的過(guò)程，從 len/2 處開(kāi)始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)，此處 len 是堆中元素的個(gè)數(shù)。建堆的過(guò)程是線性的過(guò)程，從 len/2 到 0 處一直調(diào)用調(diào)整堆的過(guò)程，相當(dāng)于 o(h2) + o(h3) …+ o(hlen/2) 其中 h 表示節(jié)點(diǎn)的深度， len/2 表示節(jié)點(diǎn)的個(gè)數(shù)，這是一個(gè)求和的過(guò)程，結(jié)果是線性的 O(n)。

②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過(guò)程中會(huì)用到，而且在堆排序過(guò)程中也會(huì)用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn) left(i) , right(i)，選出三者較大(或者最小)者，如果較大（小）值不是節(jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過(guò)程，這是一個(gè)遞歸的過(guò)程。調(diào)整堆的過(guò)程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是 lgn 的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。

③堆排序：堆排序是利用上面的兩個(gè)過(guò)程來(lái)進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)，將前面 len-1 個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過(guò)程，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出。堆排序過(guò)程的時(shí)間復(fù)雜度是 O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是 O(n)（調(diào)用一次）；調(diào)整堆的時(shí)間復(fù)雜度是 lgn，調(diào)用了 n-1 次，所以堆排序的時(shí)間復(fù)雜度是 O(nlgn)。

在這個(gè)過(guò)程中是需要大量的圖示才能看的明白的，但是我懶。。。。。。

算法實(shí)現(xiàn)：

<?php
//堆排序（對(duì)簡(jiǎn)單選擇排序的改進(jìn)）
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//調(diào)整 $arr[$start]的關(guān)鍵字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成為一個(gè)大根堆（根節(jié)點(diǎn)較大的完全二叉樹(shù)）
//注意這里節(jié)點(diǎn) s 的左右孩子是 2*s + 1 和 2*s+2 （數(shù)組開(kāi)始下標(biāo)為 0 時(shí)）
function HeapAdjust(array &$arr,$start,$end){
  $temp = $arr[$start];
  //沿關(guān)鍵字較大的孩子節(jié)點(diǎn)向下篩選
  //左右孩子計(jì)算（我這里數(shù)組開(kāi)始下標(biāo)識(shí) 0）
  //左孩子2 * $start + 1，右孩子2 * $start + 2
  for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
    if($j != $end && $arr[$j] < $arr[$j + 1]){
      $j ++; //轉(zhuǎn)化為右孩子
    }
    if($temp >= $arr[$j]){
      break; //已經(jīng)滿足大根堆
    }
    //將根節(jié)點(diǎn)設(shè)置為子節(jié)點(diǎn)的較大值
    $arr[$start] = $arr[$j];
    //繼續(xù)往下
    $start = $j;
  }
  $arr[$start] = $temp;
}
function HeapSort(array &$arr){
  $count = count($arr);
  //先將數(shù)組構(gòu)造成大根堆（由于是完全二叉樹(shù)，所以這里用floor($count/2)-1，下標(biāo)小于或等于這數(shù)的節(jié)點(diǎn)都是有孩子的節(jié)點(diǎn))
  for($i = floor($count / 2) - 1;$i >= 0;$i --){
    HeapAdjust($arr,$i,$count);
  }
  for($i = $count - 1;$i >= 0;$i --){
    //將堆頂元素與最后一個(gè)元素交換，獲取到較大元素（交換后的最后一個(gè)元素），將較大元素放到數(shù)組末尾
    swap($arr,0,$i);
    //經(jīng)過(guò)交換，將最后一個(gè)元素（較大元素）脫離大根堆，并將未經(jīng)排序的新樹(shù)($arr[0...$i-1])重新調(diào)整為大根堆
    HeapAdjust($arr,0,$i - 1);
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

運(yùn)行結(jié)果：

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

時(shí)間復(fù)雜度分析：

它的運(yùn)行時(shí)間只要是消耗在初始構(gòu)建對(duì)和在重建堆屎的反復(fù)篩選上。

總體上來(lái)說(shuō)，堆排序的時(shí)間復(fù)雜度是 O(nlogn)。由于堆排序?qū)υ加涗浀呐判驙顟B(tài)并不敏感，因此它無(wú)論是好、最差和平均時(shí)間復(fù)雜度都是 O(nlogn)。這在性能上顯然要遠(yuǎn)遠(yuǎn)好于冒泡、簡(jiǎn)單選擇、直接插入的 O(n^2) 的時(shí)間復(fù)雜度了。

堆排序是一種不穩(wěn)定排序方法。

看完了這篇文章，相信你對(duì)“PHP排序算法之堆排序Heap Sort的示例分析”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

網(wǎng)站名稱：PHP排序算法之堆排序HeapSort的示例分析-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)網(wǎng)址：http://muchs.cn/article18/dhiidp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、建站公司、定制網(wǎng)站、網(wǎng)站建設(shè)、微信小程序、動(dòng)態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)