算法引進：

在這里我直接引用《大話數據結構》里面的開頭：

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

可惜的是，這樣的操作并沒有把每一趟的比較結果保存下來，在后一趟的比較重，有許多比較在前一趟已經做過了，但由于前一趟排序時未保存這些比較結果，所以后一趟排序時又重復執行了這些比較操作，因而記錄的比較次數較多。

如果可以做到每次在選擇到最小記錄的同時，并根據比較結果對其他記錄做出相應的調整，那樣排序的總體效率就會非常高了。而堆排序，就是對簡單選擇排序進行的一種改進，這種改進的效果是非常明顯的。

基本思想：

在介紹堆排序之前，我們先來介紹一下堆：

《大話數據結構》里的定義：堆 是具有下列性質的完全二叉樹：每個節點的值都大于或等于其左右孩子節點的值，成為大頂堆（大根堆）；或者每個節點的值都小于或等于其左右節點的值，成為小頂堆（小根堆）。

當時我在看到這里的時候也對有“堆是否是完全二叉樹”有過疑問，網上也有說不是完全二叉樹的，但是無論堆是不是完全二叉樹，尚且保留意見。我們只要知道，在這里我們采用完全二叉樹形式的大根堆（小跟堆），主要是為了方便存儲和計算（后面我們會看到帶來的便利）。

堆排序算法：

堆排序就是利用堆（假設利用大根堆）進行排序的方法，它的基本思想是：將待排序的序列構造成一個大根堆。此時，整個序列的最大值就是堆頂的根節點。將它移走（其實就是將其與堆數組的末尾元素交換，此時末尾元素就是最大值），然后將剩余的 n - 1 個序列重新構造成一個堆，這樣就會得到 n 個元素中的次小的值。如此反復執行，便能得到一個有序序列了。

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

①建堆，建堆是不斷調整堆的過程，從 len/2 處開始調整，一直到第一個節點，此處 len 是堆中元素的個數。建堆的過程是線性的過程，從 len/2 到 0 處一直調用調整堆的過程，相當于 o(h1) + o(h2) …+ o(hlen/2) 其中 h 表示節點的深度， len/2 表示節點的個數，這是一個求和的過程，結果是線性的 O(n)。

②調整堆：調整堆在構建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節點i和它的孩子節點 left(i) , right(i)，選出三者最大(或者最小)者，如果最大（?。┲挡皇枪濣ci而是它的一個孩子節點，那邊交互節點i和該節點，然后再調用調整堆過程，這是一個遞歸的過程。調整堆的過程時間復雜度與堆的深度有關系，是 lgn 的操作，因為是沿著深度方向進行調整的。

③堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據元素構建堆。然后將堆的根節點取出(一般是與最后一個節點進行交換)，將前面 len-1 個節點繼續進行堆調整的過程，然后再將根節點取出，這樣一直到所有節點都取出。堆排序過程的時間復雜度是 O(nlgn)。因為建堆的時間復雜度是 O(n)（調用一次）；調整堆的時間復雜度是 lgn，調用了 n-1 次，所以堆排序的時間復雜度是 O(nlgn)。

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

算法實現：

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

時間復雜度分析：

它的運行時間只要是消耗在初始構建對和在重建堆屎的反復篩選上。

總體上來說，堆排序的時間復雜度是 O(nlogn)。由于堆排序對原始記錄的排序狀態并不敏感，因此它無論是最好、最差和平均時間復雜度都是 O(nlogn)。這在性能上顯然要遠遠好于冒泡、簡單選擇、直接插入的 O(n^2) 的時間復雜度了。

堆排序是一種不穩定排序方法。

本篇博客參考自《大話數據結構》，在此僅作記錄，方便以后查閱，大神勿噴！

PHP簡單選擇排序算法學習

微信跳一跳php代碼實現詳解

php實現的微信分享到朋友圈并記錄分享次數功能的講解

以上就是PHP實現排序堆排序算法的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。