堆排序法

堆排序

堆排序是利用堆這種資料結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞，最好，平均時間複雜度均為O(nlogn)，它也是不穩定排序。首先簡單了解下堆結構。

堆

堆是具有以下性質的完全二元樹：每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。

推薦課程：PHP教學。

如下圖：

同時，我們將堆中的結點按層編號，將這個邏輯結構映射到陣列中就是下面這個樣子

該陣列從邏輯上來說就是一個堆疊結構，我們用簡單的公式來描述一下堆的定義就是：

大頂堆：arr[i] >= arr[2i 1] && arr[i] >= arr[2i 2]  

小頂堆：arr[i]

堆排序的基本想法是：

將待排序序列建構成大頂堆，此時，整個序列的最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然後將剩餘n-1個元素重新建構成一個堆，這樣會得到n個元素的次小值。如此反覆執行，便能得到一個有序序列了

以上是堆排序法的詳細內容。更多資訊請關注PHP中文網其他相關文章！