排序算法之---堆排序（很重要的一個結構，新手入門必備）

先來簡單的介紹一下堆結構：

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

　堆是具有以下性質的完全二叉樹：

每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；

每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。

如下圖：

大根堆和小根堆在數組中的特點如下：

大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ?（i是指父節點，2i+1是子節點）

小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] ?

下面就來介紹一下堆排序的基本思想和步驟：

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

（1）將待排序的序列構造成一個大根堆：

將數組一個一個插入大根堆中：當插入的元素比起父節點大的時候，與父節點交換，并且將父節點的索引賦值給子節點，不斷地 往上遞歸上去比較。

舉個粟子：

當插入9的時候，比較完發現9還比交換后的父節點大，那就還要繼續交換了。

（2）構成大根堆之后，此時整個序列最大值就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構造成一個堆。

54~58這幾行表示的是：這個時候就要將較大的子節點與父節點進行比較了，如果子節點更大的話，那就交換父節點和子節點

59~60行這里則表示，當子節點比其父節點還大的時候，交換它們兩個的位置，同時，將index指針往下傳，繼續判斷是否有比父節點還大的子節點。

參考：https://www.cnblogs.com/chengxiao/p/6129630.html，這篇博文寫的很清晰，只是不同的是，大根堆的形成不是很相同。可以參考，很詳細。

總結

以上是生活随笔為你收集整理的排序算法之---堆排序（很重要的一个结构，新手入门必备）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。