1. 先驗知識

堆排序，是使用一種 堆 數(shù)據(jù)結(jié)構(gòu)的排序算法。在了解堆排序前，建議先掌握二叉樹相關(guān)知識，不然很費勁，很迷茫。

好了，話不多說。接下來先講一講 堆 這種數(shù)據(jù)結(jié)構(gòu)的特點。主要有兩點：①堆是一顆完全二叉樹；②堆有大頂堆和小頂堆之分。

1.1 滿二叉樹

在講完全二叉樹之前，需要先了解一下 滿二叉樹，滿二叉樹就是一顆二叉樹，每一層的節(jié)點都是“滿”的，如下圖。

?

1.2 完全二叉樹

將樹中的節(jié)點從上至下，從左至右順序編號，如果和滿二叉樹相同編號節(jié)點的位置相同，那么就是完全二叉樹，如下圖。

?

1.3 大頂堆和小頂堆

大頂堆，很明顯就是頂點數(shù)據(jù)比較大的堆；小頂堆則是頂點數(shù)據(jù)比較小的堆。話不多說，看圖。

?

2. 堆排序

好了，第一節(jié)費了點時間，如果還不夠詳細(xì)的地方，可以評論或者自己網(wǎng)頁搜索一下哈，再不進(jìn)入主題，黃花菜都涼了。不知道大家根據(jù)前面講解的大頂堆和小頂堆得到什么結(jié)論沒有？如果沒有結(jié)論，那我這里幫你總結(jié)一下，主要有兩點：①大頂堆和小頂堆從上至下，從左至右不是完全有序的，如上面大頂堆掃描得到 {34, 18, 23, 12, 8}；小頂堆得到 {3, 9, 7, 9, 12}；②大頂堆的根節(jié)點是最大值，小頂堆的根節(jié)點是最小值。

根據(jù)大頂堆的根節(jié)點是最大值這個特性，我們可以通過得到大頂堆，取出根節(jié)點，然后循環(huán)調(diào)整大頂堆取出根節(jié)點即可得到有序數(shù)列。同理，小頂堆也可以。一般大頂堆適用于升序排序，小頂堆適用于降序排序，不是很好分析為什么，下面走一遍你就會體會到，如果沒有體會，我們后面再分析；

2.1 堆排序原理

?以大頂堆對數(shù)組進(jìn)行升序排序為例。

① 將待排序數(shù)組調(diào)整為大頂堆；

② 此時根節(jié)點是最大值，交換根節(jié)點(數(shù)組首元素)和末尾節(jié)點(數(shù)組待排序元素的最后一個元素，示例會詳細(xì)說明)；

③ 因為根節(jié)點和末尾節(jié)點交換了數(shù)據(jù)，需要重新對根節(jié)點開始遞歸調(diào)整，其它節(jié)點沒有變化不需要調(diào)整；

④ 重復(fù)第②和③步驟，直到最后剩下一個待排序元素。

到這是不是有點理解堆排序的原理，什么？還是一臉懵！那就只能開始分析示例了，接下來我們實際走一遍堆排序的流程。

?

2.2 堆排序示例

假設(shè)初始無序數(shù)組arr =?{3, 9, 13, 7, 1, 16, 3, 11}，根據(jù)完全二叉樹的構(gòu)建規(guī)則，得到數(shù)組對應(yīng)的完全二叉樹形式如下。

?

2.2.1 將數(shù)組調(diào)整為大頂堆

① 得先將該數(shù)組調(diào)整為大頂堆形式對應(yīng)的數(shù)組，怎么將完全二叉樹調(diào)整為大頂堆呢？我們知道大頂堆的節(jié)點值要大于或等于子節(jié)點值，所以我們得從樹的最底層開始，慢慢地把數(shù)值大的節(jié)點往上放，最終最大值放在根節(jié)點。

② 我們從哪個節(jié)點開始調(diào)整呢？對于每一個節(jié)點，它要和子節(jié)點比較，判斷是否小于子節(jié)點，如果小于子節(jié)點則交換，否則不調(diào)整。所以我們從擁有子節(jié)點的節(jié)點開始，也就是非葉子節(jié)點。

③ 通過完全二叉樹的結(jié)構(gòu)圖，我們知道是從 第三層的7 開始調(diào)整。但如果是寫代碼，那我們怎么“確定”是 第三層的7 呢？

④ 得益于完全二叉樹的結(jié)構(gòu)，下標(biāo)為index的節(jié)點，它的父節(jié)點下標(biāo)是 (index - 1) / 2，左子節(jié)點下標(biāo)是 2 * index + 1，右子節(jié)點下標(biāo)是 2 * index + 2；完全二叉樹的最后一個節(jié)點，它肯定沒有子節(jié)點，那么我們可以有個策略：從完全二叉樹的最后一個節(jié)點往前遍歷，每次遍歷一個節(jié)點，我們就尋找它的父節(jié)點，然后父節(jié)點和左右子節(jié)點進(jìn)行比較、調(diào)整，直到根節(jié)點。這樣最終我們就能得到一個大頂堆。

⑤ 第一次，我們從完全二叉樹最后一個節(jié)點開始，它在數(shù)組的下標(biāo)是 arr.length - 1 = 7，它的父節(jié)點在數(shù)組arr中的下標(biāo)可推算得?(arr.length - 1 - 1) / 2 = 3，剛好是完全二叉樹 第三層的7 的編號。

⑤ 完全二叉樹 第三層的7 小于左子節(jié)點 第四層的11，也就是數(shù)組 arr[3]?< arr[2 * 3 + 1]；所以交換，得到 arr = {3, 9, 13, 11, 1, 16, 3, 7}，對應(yīng)的完全二叉樹如下

?

⑥ 第二次，我們從完全二叉樹倒數(shù)第二個節(jié)點分析，也就是數(shù)組索引往前，指向 arr.length - 2 = 6，它的父節(jié)點在數(shù)組下標(biāo)可推算得 (arr.length - 2 -1) / 2 = 2，指向完全二叉樹?第二層的13。

⑦ 由于完全二叉樹 第二層的13 小于左子節(jié)點 第三層的16，也就是 arr[2] < arr[2 * 2 + 1]?，交換得 arr = {3, 9, 16, 11, 1, 13, 3, 7}，對應(yīng)的完全二叉樹如下

?

⑧ 接下來同樣處理即可，就不再具體描述，以下只做簡單分析。

⑨ 第三次，完全二叉樹倒數(shù)第三個節(jié)點 第三層的13 ，也就是數(shù)組索引為 arr.length - 3 = 5，該節(jié)點的父節(jié)點 第二層16 ，數(shù)組的下標(biāo)是 (arr.length - 3 - 1) / 2 = 2。滿足條件不需要調(diào)整。

⑩ 第四次，完全二叉樹倒數(shù)第四個節(jié)點 第三層的1?，也就是數(shù)組索引為 arr.length - 4?= 4，該節(jié)點的父節(jié)點是 第二層9?，數(shù)組的下標(biāo)是 (arr.length - 4 - 1) / 2 = 1。

11. 由于 第二層的9 小于左子節(jié)點 第三層的11， 也就是 arr[1] < arr[1 * 2 + 1]，進(jìn)行交換；交換完之后，得到 arr = {3, 11, 16, 9, 1, 13, 3, 7}，對應(yīng)的完全二叉樹如下。

?

12. 此時還應(yīng)遞歸判斷完全二叉樹剛交換完得到的 第三層的9 是不是符合大頂堆要求，我們這個示例剛好符合，則結(jié)束遞歸，否則要遞歸判斷并調(diào)整。

13.?第五次，完全二叉樹倒數(shù)第五個節(jié)點 第三層的9?，也就是數(shù)組索引為 arr.length - 5?= 3，該節(jié)點的父節(jié)點是 第二層11?，數(shù)組的下標(biāo)是 (arr.length - 5 - 1) / 2 = 1。滿足條件不需要調(diào)整。

14.?第六次，完全二叉樹倒數(shù)第六個節(jié)點 第二層的16?，也就是數(shù)組索引為 arr.length - 6?= 2，該節(jié)點的父節(jié)點是 根節(jié)點3?，數(shù)組的下標(biāo)是 (arr.length - 6 - 1) / 2 = 0。

15. 由于 根節(jié)點3?小于右子節(jié)點 第二層的16， 也就是 arr[0] < arr[0 * 2 + 2]，進(jìn)行交換；交換完之后，得到 arr = {16, 11, 3, 9, 1, 13, 3, 7}，對應(yīng)的完全二叉樹如下。

?

16. 此時還應(yīng)遞歸判斷完全二叉樹剛交換完得到的 第二層的3 是不是符合大頂堆要求，我們發(fā)現(xiàn)節(jié)點 第二層的3 小于左子節(jié)點 第三層13，也就是 arr[0 * 2 + 2] < arr[(0 * 2 + 2) * 2 + 1]，進(jìn)行交換。

17. 交換后得到 arr = {16, 11, 13, 9, 1, 3, 3, 7}，對應(yīng)的完全二叉樹如下。

?

18. 遞歸判斷剛交換完的 第三層3 是不是符合大頂堆要求，我們發(fā)現(xiàn)它沒有子節(jié)點，并且推算的子節(jié)點下標(biāo)超出了數(shù)組的末尾索引，結(jié)束遞歸。

19. 因為我們剛剛調(diào)整的就是根節(jié)點，所以結(jié)束掃描。最終大頂堆結(jié)構(gòu)圖如上圖所示，數(shù)組?arr = {16, 11, 13, 9, 1, 3, 3, 7}

至此，我們完成了一次數(shù)組調(diào)整為大頂堆的流程。

?

但是上面的分析是從最后一個節(jié)點慢慢往前掃描、調(diào)整，效率有點低。但事實上由于完全二叉樹的特點，我們可以直接從最后一個節(jié)點(一定是葉子節(jié)點)的父節(jié)點(這個節(jié)點是完全二叉樹的最后一個非葉子節(jié)點，它后面的節(jié)點都是葉子節(jié)點，不用調(diào)整)開始往前掃描、調(diào)整。可以仔細(xì)思考、理解一下，我就不詳細(xì)解釋了。

?

2.2.2 將大頂堆的根節(jié)點與末尾節(jié)點進(jìn)行交換

在進(jìn)行了2.2.1之后，我們得到了大頂堆，此時我們需要保存大頂堆根節(jié)點(最大值)，保存之后，我們還需要對剩下的數(shù)據(jù)進(jìn)行調(diào)整得到大頂堆，再保存大頂堆根節(jié)點，周而復(fù)始，直到最后只有一個元素，此時不需要再排序，結(jié)束。問題來了，每次保存大頂堆根節(jié)點很簡單，我們可以新建一個數(shù)組，然后依次將數(shù)據(jù)保存在該數(shù)組即可。我們同時需要將該根節(jié)點從數(shù)組中“刨除”，然后對剩余數(shù)據(jù)繼續(xù)調(diào)整為大頂堆。如我們上面得到的數(shù)組為{16, 11, 13, 9, 1, 3, 3, 7}，如果把數(shù)組首元素“刨除”，也就是“刨除”大頂堆根節(jié)點。那么我們接下來需要對剩余元素{11, 13, 9, 1, 3, 3, 7}進(jìn)行排序，我們需要重新構(gòu)建完全二叉樹，并且調(diào)整為大頂堆，然后保存大頂堆根節(jié)點，然后再將該元素“刨除”，周而復(fù)始對剩余數(shù)據(jù)構(gòu)建、調(diào)整。

?

但是這樣有點復(fù)雜，效率不夠高，因為我們第一次得到的大頂堆是大致有序的，如果后續(xù)每次都要“刨除”根節(jié)點，重新構(gòu)建、調(diào)整的話，效率大打折扣。所以這里有一個操作：直接將數(shù)組首元素和數(shù)組末尾元素進(jìn)行交換。這樣交換之后，我們只對數(shù)組下標(biāo)為?0——arr.length-2 的元素進(jìn)行調(diào)整，并且只需要對大頂堆的根節(jié)點遞歸調(diào)整即可，因為其它的節(jié)點經(jīng)過第一次調(diào)整已經(jīng)滿足大頂堆的需求，這樣既簡單又高效。

?

2.3 堆排序的Java代碼

分析了這么多，終于來到了碼代碼階段，以下是Java的堆排序代碼、相關(guān)代碼解釋以及排序效果，如下圖。

?

總結(jié)

以上是生活随笔為你收集整理的手把手详解堆排序，堆就这么难懂？没有人看一遍学不会的，如果学不会，那就两遍吧的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。